var

father:array[1..5000]of integer;

i,j,k,p,n,m:integer;

Function getfather(v:integer):integer;

begin

if father[v]=v then exit(v);

father[v]:=getfather(father[v]);

getfather:=father[v];

end;

Procedure merge(x,y:integer);

begin

x:=getfather(x);

y:=getfather(y);

father[x]:=y;

end;

Function judge(x,y:integer):boolean;

begin

x:=getfather(x);

y:=getfather(y);

If x=y then exit(true)

else exit(false);

end;

begin

readln(n,m,p);

for i:=1 to n do

father[i]:=i;{yu chuli}

for i:=1 to m do

begin

read(j,k);

merge(j,k);

end;

for i:=1 to p do

begin

read(j,k);

if judge(j,k) then writeln('Yes')

else writeln('No')

end;

end.

函数、过程的中文意思就是作用

开个HASH记录一下每个人所属的群体，输入XY后判断HASH[X]和HASH[Y]是否相同，相同输出YES，不同输出NO

var father:array[0..5001] of longint;

n,m,p:longint;

function getfather(v:longint):longint;

begin

if v=father[v] then exit(v);

father[v]:=getfather(father[v]);

exit(father[v]);

end;

procedure main;

var i,k,j,l,r,fl,fr:longint;

begin

readln(n,m,p);

for i:=1 to n do father[i]:=i;

for i:=1 to m do

begin

readln(l,r);

fl:=getfather(l); fr:=getfather(r);

if flfr then father[fl]:=fr;

end;

for i:=1 to p do

begin

readln(l,r);

if getfather(l)getfather(r) then writeln('No') else writeln('Yes');

end;

end;

begin

main;

end.

并查集之所以难,是因为应用广泛...

有些题很难看出是并查集...

看出并查集也未必圆满...

不信做做P1152...

直接用冰茶（并查）集算法做，但是要加入路径压缩！！！

#include

#include

#include

#define MAXN 5001

#define INO void

using namespace std;

int father[MAXN],n,m,p;

string name[MAXN];

int getfather(int v){

if (father[v]==v)

return v;

father[v]=getfather(father[v]);

return father[v];

}

bool same(int x,int y){

return (getfather(x)==getfather(y));

}

INO judge(int x,int y){

int fx,fy;

fx=getfather(x);

fy=getfather(y);

if (fx==fy) return ;

father[fx]=fy;

}

INO init(){

cin>>n>>m>>p;

for (int i=1;ia>>b;

judge(a,b);

}

for (int i=0;i>b;

if (same(a,b))

cout

我用图做，前4个通过，后面超时

郁闷

type arr=record

link:longint;

v:array[1..5000] of boolean;

end;

var a:array[1..5000] of arr;

x,y,i,j,k,t,n,m,p:longint;

begin

readln(n,m,p);

for i:=1 to n do

begin

for j:=1 to n do a[i].v[j]:=false;

a[i].v[i]:=true;

a[i].link:=i;

end;

for i:=1 to m do

begin

readln(x,y);

if (not a[a[x].link].v[y]) and (not a[a[y].link].v[x]) then

for j:=1 to n do if a[a[y].link].v[j] then a[a[x].link].v[j]:=true;

for j:=1 to n do if a[a[y].link].v[j] then a[j].link:=a[x].link;

end;

for i:=1 to p do

begin

readln(x,y);

if a[a[x].link].v[y] or a[a[y].link].v[x] then writeln('Yes')

else writeln('No');

end;

end.

var

f:array[1..5000] of longint;

n,m,p,i,x,y:longint;

function fi(k:longint):longint;

begin

if f[k]=k

then exit(k);

f[k]:=fi(f[k]);

exit(f[k]);

end;

procedure union(x,y:longint);

var e1,e2:longint;

begin

e1:=fi(x);

e2:=fi(y);

if e2e1

then f[e1]:=e2;

end;

Begin

readln(n,m,p);

for i:=1 to n do

f[i]:=i;

for i:=1 to m do

begin

readln(x,y);

union(x,y);

end;

for i:=1 to p do begin

readln(x,y);

if fi(x)=fi(y)

then writeln('Yes')

else writeln('No');

end;

end.

又是并查集..

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

压缩路径的并查集

寻找父节点

function getf(w:integer):integer;

begin

if f[w]=w then getf:=w

else begin

getf:=getf(f[w]);

f[w]:=getf; {路径压缩}

end;

end;

连接X，Y

procedure int(x,y:integer);

var

xx,yy:integer;

begin

xx:=getf(x);

yy:=getf(y);

f[xx]:=yy;

end;

var

a:array[1..5000]of integer;

i,j,k,m,n,p,x,y,h1,h2:integer;

procedure find1(xx:integer);

begin

if a[xx]=0then begin h1:=xx;exit;end

else begin find1(a[xx]);a[xx]:=h1;end

end;

procedure find2(xx:integer);

begin

if a[xx]=0then begin h2:=xx;exit;end

else begin find2(a[xx]);a[xx]:=h2;end

end;

begin

readln(n,m,p);

fillchar(a,sizeof(a),0);

for i:=1 to m do

begin

read(x,y);

if (a[x]=0)and(a[y]=0)then a[y]:=x

else if(a[x]=0)and(a[y]0)then a[x]:=y

else if(a[y]=0)and(a[x]0)then a[y]:=x

else if(a[x]0)and(a[y]0)then

begin

find1(a[x]);find2(a[y]);

if h1h2 then a:=h1;

end;

end;

for i:=1 to p do

begin

read(x,y);

if (a[x]=0)and(a[y]=0)then writeln('No')

else if(a[x]=0)and(a[y]0)then begin find2(a[y]);if h2=x then writeln('Yes')else writeln('No')end

else if(a[y]=0)and(a[x]0)then begin find1(a[x]);if h1=y then writeln('Yes')else writeln('No')end

else if(a[x]0)and(a[y]0)then

begin

find1(a[x]);find2(a[y]);

if h1=h2 then writeln('Yes')

else if h1h2 then writeln('No');

end;

end;

end.

编译通过...

├ 测试数据 01：运行时错误...| 错误号: 202 | 堆栈溢出错

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：运行时错误...| 错误号: 202 | 堆栈溢出错

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：运行时错误...| 错误号: 202 | 堆栈溢出错

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：70 有效耗时：0ms

这实在是我自己写的并查集，绝对没有看书。

为什么。。。

还是不对。。。。。

var

fa:array[1..5000] of integer;

a,b,n,m,p,i,x:integer;

function gen(x:integer):integer;

begin

if fa[x]=0 then exit(x);

gen:=gen(fa[x]);

end;

function check(x,y:integer):boolean;

begin

if gen(x)=gen(y) then check:=true

else check:=false;

end;

procedure hb(x,y:integer);

begin

fa[gen(x)]:=gen(y);

end;

begin

readln(n,m,p);

for i:=1 to m do

begin

readln(a,b);

if not check(a,b) then hb(a,b);

end;

for i:=1 to p do

begin

readln(a,b);

if check(a,b) then writeln('Yes')

else writeln('No');

end;

end.

囧下……

用floyd挂得非常凄惨~~~~30分~~严重超时！！！！！

并查集实在是个很可爱的东西~~ so快~~

感觉稍微明白一些并查集了...~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：0ms

哪位大牛能帮我看下

var a:array[1..5000]of integer;

b,c:array[1..5000,1..2]of integer;

n,m,p,o,q,i,j:integer;

begin

readln(n,m,p);

for i:= 1 to m do

readln(b,b);

for i := 1 to p do

readln(c,c);

o:=1;

fillchar(a,sizeof(a),0);

for i := 1 to m do

begin

if (a[b]>0) and (a[b]>0) and (a[b]a[b]) then

begin

q:=a[b];

for j:= 1 to n do

if a[j]=q then a[j]:=a[b];

end

else

if (a[b]0)and(a[b]=0) then a[b]:=a[b]

else if (a[b]0)and(a[b]=0) then a[b]:=a[b]

else if (a[b]=0) and (a[b]= 0) then

begin

a[b]:=o;

a[b]:=o;

o:=o+1;

end;

end;

for i:=1 to p do

if (a[c]=a[c])and (a[c]0) then writeln('Yes') else writeln('No');

end.

program Ltr;

var c:array[1..5000] of integer;

i,j,m,n,p,tp1,tp2:longint;

function back(x:longint):longint;

begin

if c[x]=x then exit(x) else exit(back(c[x]));

end;

begin

readln(n,m,p);

for i:=1 to n do c[i]:=i;

for i:=1 to m do begin

readln(tp1,tp2);

c[back(tp2)]:=back(tp1);

end;

for i:=1 to p do begin

readln(tp1,tp2);

if back(tp1)=back(tp2)then writeln('Yes')

else writeln('No');

end;

end.

自己写的第一道并查集！经典！

看来确实需要加强下我的并查集了，这么道题都交了4次。。。

var

f:array[1..5000] of longint;

n,m,p,i,x,y:longint;

function find(k:longint):longint;

begin

if f[k]=k then exit(k);

f[k]:=find(f[k]);

exit(f[k]);

end;

procedure union(x,y:longint);

var e1,e2:longint;

begin

e1:=find(x); e2:=find(y);

if e2e1 then f[e1]:=e2;

end;

Begin

readln(n,m,p);

for i:=1 to n do f[i]:=i;

for i:=1 to m do begin

readln(x,y);

union(x,y);

end;

for i:=1 to p do begin

readln(x,y);

if find(x)=find(y) then writeln('Yes')

else writeln('No');

end;

end.