geray_king @ 2019-03-03 21:19:48
T了2 9 10 三个点,怎么破
#include<bits/stdc++.h>
using namespace std;
int f[10010];
int n,m;
int find_father(int x)
{
if(f[x]==x)return x;
return find_father(f[x]);
}
/*void Union(int x,int y)
{
int a1=find_father(x);
int b=find_father(y);
if(a1!=b)
f[b]=f[a1];
}*/
int main()
{ cin>>n>>m;
for(int i=1;i<=n;i++)
{
f[i]=i;
}
for(int i=0;i<m;i++)
{ int a,s,d;
cin>>a>>s>>d;
if(a==1)
{
f[find_father(s)]=find_father(d);
}
if(a==2)
{
if(find_father(s)==find_father(d))
printf("Y\n");
else
printf("N\n");
}
}
return 0;
}
by geray_king @ 2019-03-03 21:52:05
@Neptune_Disaster ···啥意思?
by Catalan1906 @ 2019-03-03 21:52:57
@geray_king 是在问对话啥意思还是按秩合并啥意思?
by geray_king @ 2019-03-03 21:56:25
@Neptune_Disaster 按秩合并
by Catalan1906 @ 2019-03-03 21:59:27
@geray_king 按秩合并就是按秩序合并
并查集是模拟一棵树
可以按照树高合并,同时要维护树高
可以优化到log级别