Wenchih @ 2018-10-30 21:39:39
#include<bits/stdc++.h>
using namespace std;
int N,M;
int ys[100001];
int zi,xi,yi;
void gb(int xx,int yy)// 合并
{
if(ys[xx] == ys[yy])
{
return;
}
for (int i = ys[yy];;i = ys[i])
{
if(i == ys[i])
{
ys[i] = ys[xx];
break;
}
ys[i] = ys[xx];
}
}
int find(int xx)
{
if(xx == ys[xx])
{
return xx;
}
else
{
return ys[xx] = find(ys[xx]);
}
}
int main()
{
cin.sync_with_stdio(false);
cout.tie(0);
freopen("test.in","r",stdin);
cin >> N >> M;
for (int i = 1;i <= N; i ++)
{
ys[i] = i;
}
for (int i = 1;i <= M; i++)
{
cin >> zi;
cin >> xi >> yi;
if(zi == 1)
{
gb(xi,yi);
}
else if(zi == 2)
{
if(find(xi) == find(yi))
{
cout << 'Y' << '\n';
}
else cout << 'N' << '\n';
}
}
return 0;
}
by 7KByte @ 2018-10-30 21:44:50
合并的时候是把x的root接到y的root上吧,不是直接把x接到y上吧
by Southern_way @ 2018-10-30 21:46:54
数组只要开10000吧
by Wenchih @ 2018-10-30 21:50:35
@雄英天下第一 10000也过不了
by Wenchih @ 2018-10-30 21:51:35
@Gang_Leader ys数组就是root,我都把yy的root合并到xx上了
by Southern_way @ 2018-10-30 21:53:57
@Wenchih freopen,你是认真的吗
by Southern_way @ 2018-10-30 21:54:41
@Wenchih 合并错了
by Southern_way @ 2018-10-30 21:55:21
int z,x,y;
cin >> z >> x >> y;
if (z == 1){
f[find(x)] = find(y);
}
else if (z == 2){
if (find(x) == find(y)) cout << "Y" << endl;
else cout << "N" << endl;
}
by Southern_way @ 2018-10-30 21:58:23
应该让一个的祖先成为另一个的祖先的父亲
by Wenchih @ 2018-10-30 21:58:49
@雄英天下第一 还没提交,freopen未注释
by Southern_way @ 2018-10-30 21:59:03
找祖先的过程中顺便路压