samsara_1 @ 2017-06-07 13:46:24
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int p[10005];
int find(int t)
{
return p[t] == t ? t : p[t] = find(p[t]);
}
int main()
{
int i,j,k,m,n,z,x,y;
cin >> n >> m;
for(i = 1; i <= 10000; i++)
p[i] = i;
for(i = 1; i <= m; i++)
{
cin >> z >> x >> y;
if(z == 1)
{
if(find(x) != find(y))
p[y] = x;
}
else
{
if(find(x) == find(y))
cout << "Y";
else
cout << "N";
cout << endl;
}
}
return 0;
}
by pb0207 @ 2017-06-07 15:58:43
@ 孟昭旭 进行合并操作时,为了保证复杂度,需要把p[y]=x,改为p[find(y)]=find(x)比较好。
by fanta2017 @ 2017-06-07 17:59:58
感谢,一语点醒我,让我少调2小时程序(^_^)
by JamesHen @ 2017-06-25 15:26:25
不是保证复杂度,上面那位仁兄的问题是把y并到x的集合去了,题目是合并两个集合。。。
@pb0207
by as2393125 @ 2017-08-04 21:52:58
二者没区别。
@ JamesHen