POJ 3180 - The Cow Prom

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

概要

N 頭の牛が stock tank の周りに 1, 2, ..., N の順に並んでいる．

M 本のロープがそれぞれ2頭の牛を繋いでいる．

ある牛が stock tank を中心にして回ったとき，ロープを引っぱる形で別の牛もつられて周る． このとき，時計回り・反時計回りのどちらに動いても最終的に自分の別のロープに引っぱられるようなとき， その一連のグループは正しく踊ることができる．

正しく踊ることができるグループがいくつあるか答える．

制約

• 2 <= N <= 10000
• 2 <= M <= 50000

解法

強連結成分分解でグループに分けることができる． それらグループのうち，サイズが2以上なものの数を数えればいい．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <stack>
 4 using namespace std;
 5 
 6 void scc_visit(const vector<int> *g, int v, int *scc_map, int& scc_size,/*{{{*/
 7         stack<int>& stk, bool *in_stk, int *low, 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<int*,int> strongly_connected_components(const vector<int> *g, int N)/*{{{*/
36 {
37   static int num[10000], low[10000];
38   stack<int> stk;
39   static bool in_stk[10000];
40   int time = 0;
41   static int scc_map[10000];
42   int scc_size = 0;
43   for (int v = 0; v < N; v++) {
44     if (num[v] == 0) {
45       scc_visit(g, v, scc_map, scc_size, stk, in_stk, low, num, time);
46     }
47   }
48   return make_pair(scc_map, scc_size);
49 }/*}}}*/
50 
51 int main()
52 {
53   int N, M;
54   scanf("%d %d", &N, &M);
55   static vector<int> g[10000];
56   for (int i = 0; i < M; i++) {
57     int u, v;
58     scanf("%d %d", &u, &v);
59     --u;  --v;
60     g[u].push_back(v);
61   }
62 
63   const pair<int*,int> r = strongly_connected_components(g, N);
64   static int cnt[10000];
65   for (int i = 0; i < N; i++) {
66     ++cnt[r.first[i]];
67   }
68   int ans = 0;
69   for (int i = 0; i < r.second; i++) {
70     if (cnt[i] != 1) {
71       ++ans;
72     }
73   }
74   printf("%d\n", ans);
75   return 0;
76 }