![[vijos P1023] Victoria的舞会3 [vijos P1023] Victoria的舞会3](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
这… 本来想学习一下Tarjan算法的,没想到码都码好了发现这题不是求强连通分量而是简单的连通分量…图论基础都还给老师了啊啊啊!最后深搜通通解决!
v标记是否被访问过,scc标记每个的祖先(本来想写Tarjan的才弄出这么奇葩个数组名字),w用于最后的统计。
program vijos_p1023;
var map:array[..,..] of longint;
v,w:array[..] of boolean;
n,m,t,i,ans,top:longint;
low,s,scc:array[..] of longint; procedure search(u,a:integer);
var i:integer;
begin
v[u]:=true;
for i:= to n do
if (map[u,i]<>) and (v[i]=false) then
begin
scc[i]:=a;
search(i,a);
end;
end; begin
fillchar(v,sizeof(v),false);
fillchar(w,sizeof(w),false);
fillchar(map,sizeof(map),);
readln(n);
for i:= to n do
begin
read(t);
while t<> do
begin
map[i,t]:=;
read(t);
end;
end;
for i:= to n do
if v[i]=false then
begin
scc[i]:=i;
search(i,i);
end;
for i:= to n do
begin
if w[scc[i]]=false then
begin
w[scc[i]]:=true;
inc(ans);
end;
end;
writeln(ans);
end.
Victoria的舞会3
测试数据 #0: Accepted, time = 0 ms, mem = 916 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 912 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 912 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 916 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 916 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 912 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 912 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 916 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 916 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 916 KiB, score = 10
Accepted, time = 0 ms, mem = 916 KiB, score = 100
0ms秒杀刷正确率什么的还是挺爽的。