【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; }

本文链接: http://www.luyixian.cn/news_show_103184.aspx 分享到：腾讯新浪人人网邮件收藏夹复制网址更多

上一篇：配一副适合程序员的眼镜

下一篇：hadoop的java.lang.InterruptedException

推荐资源

打卡神器

学习教程

【CodeForces - 1167C 】News Distribution（并查集）

News Distribution

相关资讯

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

推荐资源

打卡神器

学习教程

【CodeForces - 1167C 】News Distribution（并查集）

News Distribution

相关资讯

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

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