【CodeForces - 1167C 】News Distribution(并查集)

2019/7/21 21:26:21 人评论 次浏览 分类:学习教程

News Distribution

题意

大概就是分成几个小团体,给每个人用1 - n编号,当对某个人传播消息的时候,整个小团体就知道这个消息,输出 分别对1 - n编号的某个人传递消息时,有多少人知道这个消息。

Input

第一行n和m(n,m<=5*10^5) 接着m行,每行一个ki,接着ki(0<=ki<=n)个数,代表这个ki个人在一个QQ群里

Output

输出n个数,第i个代表,第ai个人知道谣言后,最多可以传播给几个人

Example

Input
7 5 3 2 5 4 0 2 1 2 1 1 2 6 7 
Output
4 4 1 4 4 2 2 
题目链接
https://vjudge.net/problem/CodeForces-1167C
并查集题型
题目可理解为输出1 - n每个号码所在团体总人数,利用并查集不断向集合添加成员,记录每个集合的人数,保存在根节点的sum[]中,查询每个节点的根节点,输出根节点sum[];
简述并查集,一看就会
AC代码
#include  #include  #include  #include  #include  #include  #include  #include  #include <string> #include  #include  #include  #include <set> #include  #define IOS ios_base::sync_with_stdio(0); cin.tie(0); #define Mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f #define MEM(x,y) memset(x,y,sizeof(x)) #define Maxn 100005*5 using namespace std; int par[Maxn];//par[i]  i的根 int sum[Maxn];//sum[i]  i集合的个数 int n,m,k; int findr(int x)//查询根 {     if(par[x]==x)         return x;     else         return par[x]=findr(par[x]); } void unite(int x,int y) {     x=findr(x);//查x,y根     y=findr(y);     if(x==y)//根相同不用管         return;     par[y]=x;//若根不同,y并入x,则y的根为x,同理x也能并入y  这里随意     sum[x]+=sum[y];//y并入x,则x的集合个数等于x集合个数+y集合个数 } int main() {     cin>>n>>m;     for(int i=1;i<=n;i++)     {         par[i]=i;         sum[i]=1;     }     while(m--)     {         cin>>k;         int a,b;         if(k>0)         {             //用第一个数与后面的书比较即可             cin>>a;             for(int i=1;i)             {                 cin>>b;                 unite(a,b);             }         }     }     for(int i=1;i<=n;i++)     {         int x=findr(i);//查根,输出这个根的集合个数         cout<" ";     }     cout<<endl;     return 0; }

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->