最后三个超了，求解

66666a @ 2017-03-30 19:28:16

var n,m,i,a,b,x,y,z:longint;
f:array[0..100000] of longint;
function find(k:longint):longint;
begin
if f[k]<>k then exit(find(f[k])) else exit(k);
end;
begin
readln(n,m);
for i:=1 to n do f[i]:=i;
for i:=1 to m do
begin
readln(z,x,y);
a:=find(x);
b:=find(y);
if z=1 then
begin
if a<>b then f[a]:=b;
end else
begin
if a=b then writeln('Y') else writeln('N');
end;
end;
end.

by XZYQvQ @ 2017-04-14 15:41:43

虽然我看不懂pascal代码。。。

应该是您没有路径压缩。。。

这是我的c++代码，给您参考一下吧。。。

#include <bits/stdc++.h>
using namespace std;
int n,m,f[10005];
int findf(int a){return a==f[a]?a:f[a]=findf(f[a]);}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1,x,y,z;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        if(x==1)f[findf(y)]=findf(z);
        else findf(y)==findf(z)?printf("Y\n"):printf("N\n");
    }
    return 0;
}

by Lyrics @ 2017-07-23 15:04:32

您好 您应该是这里错了

【倒数第7行】if a<>b then f[a]:=b;

楼上说的没错您没有路径压缩，您只是单纯地进行了一个合并，但是你这样的合并会导致您的集合越来越长，效率越来越差，而如果进行了路径压缩，则您的效率几乎可以达到O(1)【我不知道为什么，据说是玄学】，应该这么改：f[x]:=b;