本文最后更新于 798 天前,其中的信息可能已经有所发展或是发生改变。
输入格式
输入的第一行包含两个整数n, m
n代表图中的点的个数,m代表边的个数
接下来m行,每行2个正整数,表示图中连通的两点。
输出格式
输出1行,与1连通的点的集合,并按升序排列输出。
样例输入
6 3
1 2
2 3
3 4
样例输出
1 2 3 4
代码
#include<iostream>#include<map>
#include<set>
using namespace std;
const int N=10000;
const int M=100000;
int pre[N];
int find(int p)
{
if(p!=pre[p])
while(pre[p]!=pre[pre[p]])
pre[p]=pre[pre[p]];
return pre[p];
}
void merge(int x,int y)
{
pre[find(x)]=pre[find(y)];
}
void init(int n)
{
for(int i=1;i<=n;i++) pre[i]=i;
}
int main()
{
int n,m;
cin>>n>>m;
init(n);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
merge(a,b);
}
map<int,set<int>> mp;
for(int i=1;i<=n;i++)
mp[find(i)].insert(i);
for(auto i:mp[find(1)])
printf("%d ",i);
return 0;
}