282 条题解
-
0
尖端才子 LV 10 @ 2008-11-29 10:12:36
总算过了……看了看没加路径压缩……真囧！
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msvar
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提交 讨论 题解
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
并查集帅啊 -
0
bochuan007 LV 3 @ 2008-09-30 15:41:21
编译通过...
├ 测试数据 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; -
0
tianya2050 LV 3 @ 2008-09-24 20:21:02
编译通过...├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 0ms├ 测试数据 07：答案正确... 0ms├ 测试数据 08：答案正确... 0ms├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 25ms-------------------------Accepted 有效得分：100 有效耗时：25ms并查集!!
-
0
Xue Yanbing LV 3 @ 2008-09-24 14:05:03
并查集……
其实想要秒杀只用路经压缩就足够了
程序一共只需要18行…… -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms并查集，使用了路径压缩和按大小求并
-
0
accoropitor LV 3 @ 2008-09-11 17:26:25
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msunion-find-set...
-
0
编译通过...
├ 测试数据 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
用数组模拟树(并查集) -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 9ms
├ 测试数据 10：答案正确... 41ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：50ms -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 25ms
├ 测试数据 10：答案正确... 41ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：66ms -
0
虽然第一次写并查集，但是想说"我爱并查集！"~~~
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. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms并查集的基本操作,第一次写,程序其实很简洁
-
0
编译通过...
├ 测试数据 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. -
0
原始链表实现的并查集
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
尖端才子
LV 10
@ 2008-11-29 10:12:36
