有生以来做的第二道IOI题目居然也是96'的，又是一道比我还老的题目。
纯属复习或者说再学一遍Tarjan算法，本题的主要算法就是Tarjan+缩点，对于两个子问题的答案，根据解题：强连通缩点为拓扑图后，设入度为0点数为r，出度为0点数为c，则Task 1的答案就是r，这个很好理解；Task 2的答案是max(r,c)，这个理解不能，但是我自己画了几个图都是这样的。如果真的比赛时遇到这种东西就要自己推理了…
仍然觉得Tarjan很抽象，就像很久以前觉得快排很抽象一样…我也许能够记下来标程，但是Don't know why才是最大的问题，出了个变式就只能呵呵。
能优化的地方就是，可以改写邻接表了… 数据给的就是邻接表我还转成邻接矩阵还要用循环找出个next，不过幸好数据里n<=100。
program vijos_p1595;
var d,low,scc,s,c,r:array[..] of integer;
visit,ins,mark_scc:array[..] of boolean;
map,map2:array[..,..] of integer;
i,j,n,t,top,r0,c0,count_scc:integer;
function max(a,b:integer):integer;
begin
if a>b then exit(a) else exit(b);
end; function min(a,b:integer):integer;
begin
if a<b then exit(a) else exit(b);
end; procedure tarjan(u:integer);
var v:integer;
begin
visit[u]:=true;
inc(t);d[u]:=t;low[u]:=t;
inc(top);s[top]:=u;ins[u]:=true;
for v:= to n do
if map[u,v]= then
begin
if not visit[v] then
begin
tarjan(v);
low[u]:=min(low[u],low[v]);
end
else
if ins[v] then
low[u]:=min(low[u],d[v]);
end;
if d[u]=low[u] then
repeat
v:=s[top];
scc[v]:=u;
ins[v]:=false;
dec(top);
until u=v;
end; begin
fillchar(map,sizeof(map),);
fillchar(map2,sizeof(map2),);
fillchar(visit,sizeof(visit),false);
fillchar(ins,sizeof(ins),false);
fillchar(mark_scc,sizeof(mark_scc),false);
readln(n);
for i:= to n do
begin
read(t);
while t<> do
begin
map[i,t]:=;
read(t);
end;
readln;
end;
for i:= to n do
if not visit[i] then tarjan(i);
for i:= to n do
for j:= to n do
if (map[i,j]=) and (scc[i]<>scc[j]) then map2[scc[i],scc[j]]:=;
for i:= to n do
for j:= to n do
if map2[i,j]= then
begin
inc(c[i]);
inc(r[j]);
end;
count_scc:=;
for i:= to n do
if mark_scc[scc[i]]=false then
begin
inc(count_scc);
mark_scc[scc[i]]:=true;
end;
for i:= to n do
if scc[i]=i then
begin
if c[i]= then inc(c0);
if r[i]= then inc(r0);
end;
writeln(r0);
if count_scc> then writeln(max(c0,r0)) else writeln();
end.
学校网络
测试数据 #0: Accepted, time = 0 ms, mem = 776 KiB, score = 8
测试数据 #1: Accepted, time = 0 ms, mem = 776 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 780 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 780 KiB, score = 8
测试数据 #4: Accepted, time = 0 ms, mem = 776 KiB, score = 8
测试数据 #5: Accepted, time = 0 ms, mem = 776 KiB, score = 8
测试数据 #6: Accepted, time = 0 ms, mem = 776 KiB, score = 8
测试数据 #7: Accepted, time = 0 ms, mem = 780 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 780 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 780 KiB, score = 10
测试数据 #10: Accepted, time = 11 ms, mem = 780 KiB, score = 10