题解 - Vijos

0

lys_oson LV 8 @ 2008-11-04 07:55:50

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.

0

fs302 LV 8 @ 2008-11-04 15:50:36

搞了好久，参考了太多代码，搞得我头都晕了，不懂用哪个，下面的代码还好，清晰。利用树的结构来储存关系

Program bingchaji;{典型的并查集}

Const

maxn=10000;

Var

father:array[0..maxn]of longint;

n,m,p,i,j,ai,bi:longint;

Function getfather(v:longint):longint;

Begin

if father[v]=v then getfather:=v

else

begin

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

getfather:=father[v];

end;

End;

Procedure int(x,y:longint);

var

i,j:longint;

Begin

i:=getfather(x);

j:=getfather(y);

father[i]:=j;

End;

Begin

readln(n,m,p);

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

for j:=1 to m do

begin

readln(ai,bi);

int(ai,bi);

end;

for j:=1 to p do

begin

readln(ai,bi);

if getfather(ai)=getfather(bi) then writeln('Yes')

else writeln('No');

end;

End.

0

liujiahui LV 7 @ 2008-11-02 15:50:47

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program v1034;

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

n,m,x,y,i,j,p,q,a,b:longint;

function find(x:longint):longint;

var i:longint;

begin

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

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

i:=x;

while f[i]i do i:=f[i];

exit(i);

end;

procedure zip(x,q:longint);

var j:longint;

begin

if x=q then exit;

if f[x]x then zip(f[x],q);

f[x]:=q;

for j:=1 to n do if f[j]=x then f[j]:=q;

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);

if f[x]f[y] then begin

a:=find(x);b:=find(y);

f:=a;

zip(x,a);zip(y,a);

end;

end;

for i:=1 to p do begin

readln(x,y);

if f[x]=f[y] then writeln('Yes')

else writeln('No');

end;

end.

0

张烨 LV 3 @ 2008-11-01 10:03:48

var

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

i,j,x1,y1,n,m,x,y,t,q:longint;

function find(t:longint):longint;

begin

if father[t]t then

find:=find(father[t]) else

find:=father[t];

end;

begin

readln(n,m,q);

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

for i:=1 to m do

begin

readln(x,y);

x1:=find(x);

y1:=find(y);

if x1y1 then father[y1]:=x1;

end;

for i:=1 to q do

begin

readln(x,y);

if find(x)=find(y) then

writeln('Yes') else writeln('No');

end;

end.

0

O.G.Loc LV 5 @ 2008-10-29 23:21:29

(Invalid img)O,YEAH!!!

并查集还真不难..

0

king13 LV 8 @ 2008-10-22 17:41:27

大家不要用并查集

根本就没那复杂!

我就是用朴素的算法过的!

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

jtjxhjl321 LV 3 @ 2008-10-22 11:58:39

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program p1034;

var

i,j,c,n,front,rear,k,m,p,l:longint;

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

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

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

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

begin

readln(n,m,p);

for k:=1 to n do s[k]:=0;

for k:=1 to m do begin

readln(i,j);

a:=1;

a[j,i]:=1;

end;

for k:=1 to p do begin

readln(i,j);

t[k,1]:=i;

t[k,2]:=j;

end;

l:=0;

c:=n;

while c>0 do

begin

inc(l);

i:=1;

while s[i]0 do inc(i);

front:=1;

rear:=1;

d[rear]:=i;

s[i]:=l;

dec(c);

while front

0

ME.Crazy2 LV 3 @ 2008-10-20 21:15:50

Accepted 有效得分：100

0

lxyxynt LV 10 @ 2008-10-20 17:54:11

YES---|yes---|Yes--AC......

注意大小写..

0

将军 LV 3 @ 2008-10-19 21:44:44

并查集,我也知道了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

FORM 捕龟者x

0

捕龟者x LV 6 @ 2008-10-19 21:42:27

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

终于知道并查集怎么写了

0

noso LV 3 @ 2008-10-15 15:32:19

这是我第一个写一遍就AC的

呵呵

0

beakham LV 8 @ 2008-10-13 19:21:36

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

险啊！~~~~

0

huxiuhan LV 3 @ 2008-10-11 22:20:09

var

low:Array[1..5000] of longint;

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

function find(x:longint):longint;

var t:longint;

begin

t:=x;

while low[x]x do x:=low[x];

low[t]:=x; exit(x);

end;

begin

read(n,m,p);

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

for i:=1 to m do

begin

read(x,y);

low[find(x)]:=find(y);

end;

for i:=1 to p do

begin

read(x,y);

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

else writeln('No');

end;

end.

0

c7 LV 3 @ 2008-10-11 19:41:07

传递闭包只可以过5个

0

liushengxuan LV 7 @ 2008-10-11 11:09:18

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

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

function getfather(v:integer):integer;

begin

if (father[v]=0) then

getfather:=v

else

begin

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

getfather:=father[v];

end;

end;

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

var fx,fy : integer;

begin

fx := getfather(x);

fy := getfather(y);

If fx=fy then begin judge :=true;exit;end

else judge := false;

father[fx] := fy;

end;

begin

read(o,p,u);

for i:=1 to p do

begin

read(x,y);

judge(x,y);

end;

for i:=1 to u do

begin

read(x,y);

if getfather(x)=getfather(y) then writeln('Yes') else writeln('No');

end;

end.

0

zhaoyang LV 8 @ 2008-10-11 00:30:13

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

玛维-影之歌 LV 10 @ 2008-10-09 21:04:47

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第一次做并查集...AC!第一次用了Floyed也能过两个点...

0

190235047 LV 3 @ 2008-10-06 00:41:45

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

感谢题解里的牛们让我理解了并查集

0

boyzkk LV 10 @ 2008-10-05 20:34:54

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我口渴，所以………………需要水！

题解

283 条题解

家族

信息

状态

开发

支持

题解

283 条题解

家族

信息

状态

开发

支持

还没有账户？

登录