网络

一些学校连接在一个计算机网络上。学校之间存在软件支援协议。每个学校都有它应支援的学校名单（学校a支援学校ｂ，并不表示学校ｂ一定支援学校a）。当某校获得一个新软件时，无论是直接得到还是网络得到，该校都应立即将这个软件通过网络传送给它应支援的学校。因此，一个新软件若想让所有连接在网络上的学校都能使用，只需将其提供给一些学校即可。

子任务a：

请编一个程序，根据学校间支援协议（各个学校的支援名单），计算最少需要将一个新软件直接提供给多少个学校，才能使软件通过网络被传送到所有学校。

子任务ｂ：

如果允许在原有支援协议上添加新的支援关系。则总可以形成一个新的协议，使得此时只需将一个新软件提供给任何一个学校，其他所有学校就都可以通过网络获得该软件。编程计算最少需要添加几条新的支援关系。

输入数据：

第一行是一个正整数ｎ（２≤ｎ≤１００），表示与网络连接的学校总数，随后ｎ行分别表示每个学校要支援的学校，即：i+1行表示第i号学校要支援的所有学校代号，最后０结束。如果一个学校不支援任何其他学校，相应行则会有一个０。一行中若有多个数字，数字之间以一个空格分隔。

输出数据：

包含两行，第一行是一个正整数，表示子任务a的解，第二行也是一个正整数，表示子任务ｂ的解。

【输入样例】network.in

5

2 4 3 0

4 5 0

0

0

1 0

【输出样例】network.out

1

2

先将强连通分量收缩成点,对于第一问,统计入度为0的点即可,第二问,分别统计入度为0的个数与出度为0的个数,取最大值即可,因为要使图全连通,入度为0的必须有入度,出度为0的必须有出度,才能使任意一个点到达其他任何点(除了全图只有1个点的特殊情况)

将强连通分量收缩成点使用两遍深搜的Kosaraju算法.

对于一个图中的连通分量来说,它的逆图中这个连通分量依然存在,第二次DFS时依然要按上次的顺序

收缩时需重新构图

program fdfdf;
var n,i,j,x,l:longint;
    a,g,a1:array[1..100,0..100] of longint;
    b,t:array[1..100] of longint;
    ans1,ans2,d1,d2:longint;

procedure dfs(v:longint);
var i1:longint;
begin
    b[v]:=1;
    for i1:=1 to a[v,0] do
    if b[a[v,i1]]=0 then
      dfs(a[v,i1]);
    inc(l);
    t[l]:=v;
end;

procedure dfs1(v:longint);
var i1:longint;
begin
    b[v]:=l;
    for i1:=1 to a1[v,0] do
    if b[a1[v,i1]]=0 then
      dfs1(a1[v,i1]);
end;

begin
assign(input,'network.in');assign(output,'network.out');
reset(input); rewrite(output);
readln(n);
fillchar(a,sizeof(a),0);
fillchar(g,sizeof(g),0);
for i:=1 to n do
begin
    read(x);
    while x<>0 do
      begin
        inc(a[i,0]);
        a[i,a[i,0]]:=x;
        inc(a1[x,0]);
        a1[x,a1[x,0]]:=i;
        read(x);
      end;
    readln;
end;
fillchar(b,sizeof(b),0); l:=0;
for i:=1 to n do
if b[i]=0 then
    dfs(i);
fillchar(b,sizeof(b),0); l:=0;
for i:=n downto 1 do
if b[t[i]]=0 then
    begin
    inc(l);
    dfs1(t[i]);
    end;
for i:=1 to n do
for j:=1 to a[i,0] do
g[ b[i] , b[a[i,j]] ]:=1;

ans1:=0;
for i:=1 to l do
begin
    d1:=0;
    for j:=1 to l do
    if i<>J then
    if g[j,i]=1 then
      begin
        d1:=1;
        break;
      end;
    if d1=0 then inc(ans1);
end;
writeln(ans1);
ans2:=0; d2:=0;
for i:=1 to l do
    begin
      d1:=0;
      for j:=1 to l do
      if i<>j then
      if g[i,j] =1 then begin d1:=1; break; end;
      if d1=0 then
      inc(d2);
    end;
ans2:=d2; d2:=0;
for i:=1 to l do
begin
    d1:=0;
    for j:=1 to l do
    if i<>j then
      if g[j,i] =1 then begin d1:=1; break; end;
    if d1=0 then
    inc(d2);
end;
if d2>ans2 then ans2:=d2;
if l=1 then writeln(0)
else writeln(ans2);
close(input); close(output);
end.