【TOJ】并查集训练
程序员文章站
2022-07-09 18:23:10
描述 2010年是xx国一个多灾多难的一年,灾难使该国的通讯系统遭到了重创,全国共有n个通讯站点,分别从0到n-1进行编号,通讯部门对每两个站点的线路进行了检测,现在要你确定有哪些站点是彼此连通的。 2010年是xx国一个多灾多难的一年,灾难使该国的通讯系统遭到了重创,全国共有n个通讯站点,分别从0 ......
描述
2010年是xx国一个多灾多难的一年,灾难使该国的通讯系统遭到了重创,全国共有n个通讯站点,分别从0到n-1进行编号,通讯部门对每两个站点的线路进行了检测,现在要你确定有哪些站点是彼此连通的。
输入
输入数据有多组,每组数据的第一行包含两个整数n和m,其中n为通讯站点个数,接下来有m行,每一行有2个整数a和b,表示站点a和b通讯正常。其中1<=n<=250。
输入以EOF结束。
输出
针对每组输入,将所有连通的站点进行分组,并将每组按照站点从小到大的顺序输出,如果有多组,所有的组根据每组最小的站点编号进行从小到大的排序后输出。
每组数据输出之后加一个空行
样例输入
3 3
0 1
1 2
0 2
5 1
0 2
样例输出
0 1 2
0 2
1
3
4
#include<iostream> using namespace std; int top[255]; int find(int r) { if(top[r]!=r) top[r]=find(top[r]); return top[r]; } int join(int x,int y) { int fx=find(x),fy=find(y); if(fx!=fy) { top[fx]=fy; } } int init(int n) { for(int i=0;i<n;i++) top[i]=i; } int main() { int i,j,n,m,a,b; while(scanf("%d%d",&n,&m)!=EOF) { init(n); for(j=0;j<m;j++) { scanf("%d%d",&a,&b); join(a,b); } int vis[255]={0}; for(i=0;i<n;i++) { if(!vis[i]) { printf("%d",i); vis[i]=1; for(j=0;j<n;j++) { if(find(i)==find(j)&&vis[j]==0) //如果上级相同且未访问过 { printf(" %d",j); vis[j]=1; } } cout<<endl; } } cout<<endl; } return 0; }