一次性编译。。。

一次性AC。。。

总算过了……看了看没加路径压缩……真囧！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

f:array[0..5000]of integer;

function getfather(v:integer):integer;

begin

if f[v]=0 then exit(v);

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

exit(f[v]);

end;

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

begin

if getfather(x)=getfather(y)

then exit(true)

else exit(false);

end;

procedure judge(x,y:integer);

var fx,fy:integer;

begin

fx:=getfather(x);

fy:=getfather(y);

if fxfy then f[fx]:=fy;

end;

procedure main;

var

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

begin

read(n,m,k);

fillchar(f,sizeof(f),0);

for i:=1 to m do

begin

read(p,q);

judge(p,q);

end;

for i:=1 to k do

begin

read(p,q);

if same(p,q) then writeln('Yes') else writeln('No');

end;

end;

begin

main;

end.

Flag 　　 Accepted

题号 　　P1034

类型(?) 　　并查集

通过 　　2800人

提交 　　6982次

通过率 　　40%

难度 　　2

提交 讨论 题解

庆祝一下，升为两星！

有没有用C的解法- -

编译通过...

├ 测试数据 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：答案正确... 0ms

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

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

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

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

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

冰渣机。。。。路径压缩。。。但是还是有一个点9MS...

why?

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

for i:= 1 to m do

begin

readln(a,b);

if a > b then begin k:=a; a:=b; b:=k; end;

c:=re[a];

for j:= 1 to n do

if re[j]=c then

re[j]:=re;

end;

编译通过...├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 0ms├ 测试数据 07：答案正确... 0ms├ 测试数据 08：答案正确... 0ms├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 25ms-------------------------Accepted 有效得分：100 有效耗时：25ms并查集!!

并查集……

其实想要秒杀只用路经压缩就足够了

程序一共只需要18行……

一个比较简单的并查集..

No打成NO....

第二次才AC...

注意细节..

细节..

编译通过...

├ 测试数据 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：答案正确... 0ms

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

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

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

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

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

union-find-set...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

没用任何减枝也能过 SO EASY

用数组模拟树(并查集)

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

虽然第一次写并查集，但是想说"我爱并查集！"~~~

program ma;

var

n,m,p,i,j,x,y:integer;

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

begin

read(n,m,p);

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

for i:=1 to m do

begin

read(x,y);

for j:=1 to n do

if (a[y]=a[j])and(yj)then

a[j]:=a[x];

a[y]:=a[x];

end;

for i:=1 to p do

begin

read(x,y);

if a[x]=a[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

并查集的基本操作,第一次写,程序其实很简洁

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

并查集万岁！！！

var

n,m,k,i,a,b:integer;

father:array[1..5000] of 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,k);

for i:=1 to n do

father[i]:=i;

for i:=1 to m do

begin

readln(a,b);

merge(a,b);

end;

for i:=1 to k do

begin

readln(a,b);

if judge(a,b)=true then

writeln('Yes')

else

writeln('No');

end;

end.

AC80纪念题~~

并茶几很简单

原始链表实现的并查集

├ 测试数据 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：答案正确... 0ms

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

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

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

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

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