做法(BalanceGnlyYue)

并查集+路径压缩
program ms;
var a:array[1..300] of longint;
f:array[1..300] of boolean;
ans,n,i,x:longint;
function findroot(k:longint):longint;
begin
while a[k]<>k do
k:=a[k];
findroot:=k;
end;
begin
readln(n);
for i:=1 to n do
begin
a[i]:=i;
f[i]:=false;
end;
for i:=1 to n do
repeat
read(x);
if x<>0
then
if findroot(x)<>findroot(i)
then
a[findroot(i)]:=findroot(x);
until
x=0;
for i:=1 to n do
f[findroot(i)]:=true;
ans:=0;
for i:=1 to n do
if f[i]
then
inc(ans);
writeln(ans);
end.

0 条评论

目前还没有评论...

信息

ID
1022
难度
4
分类
图结构 点击显示
标签
递交数
4330
已通过
1985
通过率
46%
被复制
14
上传者