强联通块tarjan算法

浏览数：23 / 时间：2015年06月11日

http://poj.org/problem?id=1236
第一问：需要几个学校存在软件，才能通过传递，使得所有的学校都有软件
用tarjan算法求出强联通分量后，将每个联通分量缩成一个点，那么问题1的答案就是入度为0的点的个数
为什么？入度为0的点，肯定不能通过其他学校传送软件给他，所以他必须存在一份软件
第二问：需要加几条边，才能使得图强联通
缩点后，a为所有入度为0的点的个数，b为所有出度为0的点的个数，那么答案就是max(a,b)

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <vector>
 4 #include <stack>
 5 using namespace std;
 6 const int N = 100 + 10;
 7 vector<int> G[N];
 8 stack<int> st;
 9 bool vis[N];
10 int sccno[N],pre[N],lowlink[N],in[N],out[N],dfs_clock,scc_cnt;
11 int min(const int &a, const int &b)
12 {
13     return a < b ? a : b;
14 }
15 void tarjan(int u)
16 {
17     pre[u] = lowlink[u] = ++dfs_clock;
18     st.push(u);
19     for(int i=0; i<G[u].size(); ++i)
20     {
21         int v = G[u][i];
22         if(!pre[v])
23         {
24             tarjan(v);
25             lowlink[u] = min(lowlink[u],lowlink[v]);
26         }
27         else if(!sccno[v])
28             lowlink[u] = min(lowlink[u],pre[v]);
29     }
30     if(lowlink[u]==pre[u])
31     {
32         scc_cnt++;
33         for(;;)
34         {
35             int x = st.top();st.pop();
36             sccno[x] = scc_cnt;
37             if(x==u) break;
38         }
39     }
40 }
41 void find_scc(int n)
42 {
43     for(int i=1; i<=n; ++i)
44         if(!pre[i])
45             tarjan(i);
46 }
47 int main()
48 {
49     int n,i,a,b;
50     scanf("%d",&n);
51     for(a=1; a<=n; ++a)
52     {
53         while(scanf("%d",&b),b)
54         {
55             G[a].push_back(b);
56             vis[b] = true;
57         }    
58     }
59     find_scc(n);
60     for(i=1; i<=scc_cnt; ++i) in[i] = out[i] = 1;
61     for(int u=1; u<=n; ++u)
62         for(i=0; i<G[u].size();++i)
63         {
64             int v = G[u][i];
65             if(sccno[u] != sccno[v]) in[sccno[v]] = out[sccno[u]] = 0;
66         }
67     a = b = 0;
68     for(i=1; i<=scc_cnt; ++i)
69     {
70         if(in[i]) a++;
71         if(out[i]) b++;
72     }    
73     int ans = a > b ? a : b;
74     if(scc_cnt == 1) ans = 0;
75     printf("%d\n%d\n",a,ans);
76     return 0;
77 }