欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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