POJ 2186 - Popular Cows

http://poj.org/problem?id=2186

概要

N 頭の牛に関して，M 個の「A が B を popular だと思っている」という関係が与えられる． popularity は推移的であり，A が B を popular と思っていて B が C を popularだと思っていると，A は C を popular だと思っていることになる．

自分を除く全ての牛から popular だと思われている牛が何頭いるかを答える．

制約

解法

同じ強連結成分に含まれる牛はそれぞれを互いに popular だと思っているため，強連結成分を1つのノードとして縮約したグラフを考える．

そのグラフ上では当然強連結成分は無いため，1つもエッジを張っていないノードの，縮約前のノードが題意を満たすことになる．

ただし，1つもエッジを張っていないノードが複数ある場合は，明らかに題意を満たす牛は存在しない．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <stack>
 4 using namespace std;
 5 
 6 void scc_visit(const vector<vector<int> >& g, int v, vector<int>& scc_map, int& scc_size,/*{{{*/
 7     stack<int>& stk, vector<bool>& in_stk, vector<int>& low, vector<int>& num, int& time)
 8 {
 9   low[v] = num[v] = ++time;
10   stk.push(v);
11   in_stk[v] = true;
12   for (vector<int>::const_iterator it(g[v].begin()); it != g[v].end(); ++it) {
13     const int u = *it;
14     if (num[u] == 0) {
15       scc_visit(g, u, scc_map, scc_size, stk, in_stk, low, num, time);
16       low[v] = min(low[v], low[u]);
17     } else if (in_stk[u]) {
18       low[v] = min(low[v], num[u]);
19     }
20   }
21   if (low[v] == num[v]) {
22     for (;;) {
23       const int u = stk.top();
24       stk.pop();
25       in_stk[u] = false;
26       scc_map[u] = scc_size;
27       if (u == v) {
28         break;
29       }
30     }
31     ++scc_size;
32   }
33 }/*}}}*/
34 
35 pair<vector<int>,int> strongly_connected_components(const vector<vector<int> >& g)/*{{{*/
36 {
37   const int N = g.size();
38   vector<int> num(N), low(N);
39   stack<int> stk;
40   vector<bool> in_stk(N, false);
41   int time = 0;
42   vector<int> scc_map(N);
43   int scc_size = 0;
44   for (int v = 0; v < N; v++) {
45     if (num[v] == 0) {
46       scc_visit(g, v, scc_map, scc_size, stk, in_stk, low, num, time);
47     }
48   }
49   return make_pair(scc_map, scc_size);
50 }/*}}}*/
51 
52 int main()
53 {
54   int N, M;
55   scanf("%d %d\n", &N, &M);
56   vector<vector<int> > g(N);
57   for (int i = 0; i < M; i++) {
58     int a, b;
59     scanf("%d %d\n", &a, &b);
60     --a;  --b;
61     g[a].push_back(b);
62   }
63   const pair<vector<int>,int> r = strongly_connected_components(g);
64   vector<bool> refers_scc(r.second, false);
65   for (int i = 0; i < N; i++) {
66     for (vector<int>::const_iterator it(g[i].begin()); it != g[i].end(); ++it) {
67       if (r.first[i] != r.first[*it]) {
68         refers_scc[r.first[i]] = true;
69       }
70     }
71   }
72   int not_refer = 0;
73   for (int i = 0; i < r.second; i++) {
74     if (!refers_scc[i]) {
75       ++not_refer;
76     }
77   }
78   if (not_refer > 1) {
79     puts("0");
80   } else {
81     int ans = 0;
82     for (int i = 0; i < N; i++) {
83       if (!refers_scc[r.first[i]]) {
84         ++ans;
85       }
86     }
87     printf("%d\n", ans);
88   }
89   return 0;
90 }
poj/2186.cc