[Tarjan][图的强连通性]Poj P1236 Network of Schools

题目大意

有n个学校，学校之间可以传递信息，例如学校 a 可以传达信息给 b ，即a ——> b , 但 b 不一定能传递信息给 a
告诉你每个学校能够向哪些学校传递信息，然后有两个问题：
问题一：至少要向几个学校传递原始信息，才能保证所有学校都能收到信息
问题二：至少要添加多少组关系（每组关系类型如右：a 可以向 b 传递信息），才能保证给任意一个学校原始信息后，其他所有学校都能收到信息

题解

先跑一边tarjian算法。那么我们可以得出每一个学校在哪一个强连通分量里
那么知道，第一个答案就是入度为0的学校
假设有n个入度为0，m个出度为0
那么第一个答案就是n,第二个答案是max(n,m)
需要注意的是假如只有一个强连通分量，即整个图是连通的，那么第一个答案是1，第二个答案是0

代码

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 struct edge{int b,e,next;}g[3010];
 5 int head[40000],k[40000],belong[40000],low[40000],dfn[40000],z1[40000],z2[40000];
 6 int total,num,n,mx,tot,ans,ans1,ans2;
 7 bool v[40010];
 8 void insert(int x,int y)
 9 {
10     g[++tot].b=x;
11     g[tot].e=y;
12     g[tot].next=head[x];
13     head[x]=tot;
14 }
15 void tarjan(int x)
16 {
17     int y;
18     mx++;
19     dfn[x]=mx; low[x]=mx;
20     num++; k[num]=x;
21     v[x]=true;
22     for (int i=head[x];i;i=g[i].next)
23     {
24         y=g[i].e;
25         if (dfn[y]==0)
26         {
27             tarjan(y);
28             if (low[x]>low[y]) low[x]=low[y];
29         }
30         else if (v[y]&&dfn[y]<low[x]) low[x]=dfn[y];
31         
32     }
33     if (dfn[x]==low[x])
34     {
35         total++;
36         do
37         {
38             y=k[num];
39             v[y]=false;
40             num--;
41             belong[y]=total;
42         }
43         while (x!=y);
44     }
45 }
46 int main()
47 {
48     scanf("%d",&n);
49     for (int i=1;i<=n;i++)
50     {
51         int x;
52         scanf("%d",&x);
53         while (x!=0)
54         {
55             insert(i,x);
56             scanf("%d",&x);
57         }
58     }
59     for (int i=1;i<=n;i++) if (dfn[i]==0) tarjan(i);
60     for (int i=1;i<=tot;i++)
61         if (belong[g[i].b]!=belong[g[i].e])
62         {
63             z1[belong[g[i].b]]++;
64             z2[belong[g[i].e]]++;
65         }
66     for (int i=1;i<=total;i++)
67     {
68         if (z2[i]==0)
69         {
70             ans++;
71             ans1++;
72         }
73         if (z1[i]==0) ans2++;
74     }
75     printf("%d
",ans);
76     if (total==1) { ans1=0; ans2=0;    }
77     if (ans1>ans2) printf("%d",ans1);
78               else printf("%d",ans2);
79     return 0;
80 }