C. News Distribution(并查集)
In some social network, there are nn users communicating with each other in mm groups of friends. Let's analyze the process of distributing some news between users.
Initially, some user xx receives the news from some source. Then he or she sends the news to his or her friends (two users are friends if there is at least one group such that both of them belong to this group). Friends continue sending the news to their friends, and so on. The process ends when there is no pair of friends such that one of them knows the news, and another one doesn't know.
For each user xx you have to determine what is the number of users that will know the news if initially only user xx starts distributing it.
The first line contains two integers nn and mm (1≤n,m≤5⋅1051≤n,m≤5⋅105) — the number of users and the number of groups of friends, respectively.
Then mm lines follow, each describing a group of friends. The ii-th line begins with integer kiki (0≤ki≤n0≤ki≤n) — the number of users in the ii-th group. Then kiki distinct integers follow, denoting the users belonging to the ii-th group.
It is guaranteed that ∑i=1mki≤5⋅105∑i=1mki≤5⋅105.
Print nn integers. The ii-th integer should be equal to the number of users that will know the news if user ii starts distributing it.
7 5
3 2 5 4
0
2 1 2
1 1
2 6 7
4 4 1 4 4 2 2
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<map>
#include<cmath> const int maxn=5e5+;
typedef long long ll;
using namespace std;
int pre[maxn];
int find(int x)
{
if(x==pre[x])
{
return x;
}
else
{
return pre[x]=find(pre[x]);
}
}
void Merge(int x,int y)
{
int xx=find(x);
int yy=find(y);
if(xx!=yy)
{
pre[xx]=yy;
} }
int a[maxn];
int main()
{
int n,m;
cin>>n>>m;
int x;
for(int t=;t<=n;t++)
{
pre[t]=t;
}
int s1,s2;
for(int t=;t<m;t++)
{
scanf("%d",&x);
if(x!=)
scanf("%d",&s1);
for(int j=;j<x;j++)
{
scanf("%d",&s2);
Merge(s1,s2);
s1=s2;
}
} int ans=;
memset(a,,sizeof(a));
for(int t=;t<=n;t++)
{ a[find(t)]++;
}
for(int t=;t<=n;t++)
{
printf("%d ",a[find(t)]);
} return ;
}
最新文章
- kubernetes部署Fluentd+Elasticsearch+kibana 日志收集系统
- 将plist文件读取成为数组
- Hadoop学习笔记—2.不怕故障的海量存储:HDFS基础入门
- Rebalance Customer Balances Utility的使用
- Eclipse 无线调试(利用ADB工具)
- uva 818 (位运算 + 判环)
- js生成二维码实例(真实有效)
- STL简单应用问题
- http://blog.csdn.net/bluejoe2000/article/details/39521405#t9
- IE7append新的元素自动补充完整路径
- CentOS7安全设置 yum-cron系统自动更新,firewalld防火墙简单使用
- QPushButton跑进度条(使用QSS的不同修饰来实现,其实是伪进度条)
- 理解Android虚拟机体系结构(转)
- Kettle(Pentaho)实现web方式远程执行job或transformation
- Zabbix实战-简易教程--告警屏蔽(Maintenances)
- PS图片去色
- 【爆料】-《伯明翰大学学院毕业证书》UCB一模一样原件
- 【转】jira插件Zephyr的具体使用
- 重开Vue2.0
- 捕捉JDialog的关闭事件