Description
如题,现在有一个并查集,你需要完成合并和查询操作。
Input
第一行包含两个整数(N)、(M),表示共有(N)个元素和(M)个操作。
接下来M行,每行包含三个整数(opt)、(a)、(b)
当(opt=1)时,将(a)与(b)所在的集合合并
当(opt=2)时,输出(a)与(b)是否在同一集合内,是的话输出(Y);否则话输出(N)
Output
如上,对于每一个opt=2的操作,都有一行输出,每行包含一个大写字母,为Y或者N
Solution
路径压缩
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,f[10010],opt,x,y;
inline int read()
{
int ans=0;
char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9')
{
ans=ans*10+ch-'0';
ch=getchar();
}
return ans;
}
int find(int x)
{
if (f[x]==x) return x;
return f[x]=find(f[x]);
}
int main()
{
n=read(),m=read();
for (int i=1;i<=n;i++) f[i]=i;
while (m--)
{
opt=read(),x=read(),y=read();
if (opt==1)
{
int fx=find(x),fy=find(y);
if (fx!=fy) f[fx]=fy;
}
else
{
int fx=find(x),fy=find(y);
if (fx!=fy) printf("N
"); else printf("Y
");
}
}
return 0;
}
按秩合并
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,f[100010],dep[100010],opt,x,y;
inline int read()
{
int ans=0;
char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9')
{
ans=ans*10+ch-'0';
ch=getchar();
}
return ans;
}
int find(int x)
{
if (f[x]==x) return x;
return find(f[x]);
}
int main()
{
n=read(),m=read();
for (int i=1;i<=n;i++) f[i]=i,dep[i]=0;
while (m--)
{
opt=read(),x=read(),y=read();
if (opt==1)
{
int fx=find(x),fy=find(y);
if (fx==fy) continue;
if (dep[fx]<dep[fy]) f[fx]=fy;
else if (dep[fx]>dep[fy]) f[fy]=fx;
else
{
f[fx]=fy;
dep[fy]++;
}
}
else
{
int fx=find(x),fy=find(y);
if (fx!=fy) printf("N
"); else printf("Y
");
}
}
return 0;
}