POJ 1144 - Network

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

概要

頂点数 N の連結な無向グラフが与えられる．

ノードは交換局を表わし，エッジは電話線を表わしている． ある交換局が機能しなくなったときにグラフが連結でなくなるとき，その交換局は critical であると言う． critical な交換局が何個あるか答える．

制約

• N < 100

解法

critical な頂点というのは，グラフ理論の言葉では関節点と言う．

関節点は強連結成分分解のときのような DFS によって求めることができる．

 1 #include <iostream>
 2 #include <sstream>
 3 #include <vector>
 4 using namespace std;
 5 
 6 void art_visit(const vector<vector<int> >& g, int v, vector<int>& parent, vector<int>& low, vector<int>& num, int& time)/*{{{*/
 7 {
 8   low[v] = num[v] = time++;
 9   for (vector<int>::const_iterator it = g[v].begin(); it != g[v].end(); ++it) {
10     const int u = *it;
11     if (num[u] == -1) {
12       parent[u] = v;
13       art_visit(g, u, parent, low, num, time);
14       low[v] = min(low[v], low[u]);
15     } else if (u != parent[v]) {
16       low[v] = min(low[v], num[u]);
17     }
18   }
19 }/*}}}*/
20 int articulation_point(const vector<vector<int> >& g)/*{{{*/
21 {
22   const int N = g.size();
23   vector<int> num(N, -1), low(N, -1), parent(N, -1);
24   int time = 0;
25   art_visit(g, 0, parent, low, num, time);
26 
27   vector<int> is_art(N, false);
28   for (int v = 1; v < N; v++) {
29     const int u = parent[v];
30     if (u == 0) {
31       if (num[v] != 1) {
32         is_art[0] = true;
33       }
34     } else {
35       if (num[u] <= low[v]) {
36         is_art[u] = true;
37       }
38     }
39   }
40   int ans = 0;
41   for (int i = 0; i < N; i++) {
42     if (is_art[i]) {
43       ++ans;
44     }
45   }
46   return ans;
47 }/*}}}*/
48 
49 int main()
50 {
51   ios::sync_with_stdio(false);
52   int N;
53   while (cin >> N && N != 0) {
54     vector<vector<int> > g(N);
55     cin.ignore();
56     string line;
57     while (getline(cin, line) && line != "0") {
58       istringstream iss(line);
59       int u;
60       iss >> u;
61       --u;
62       for (int v; iss >> v;) {
63         --v;
64         g[u].push_back(v);
65         g[v].push_back(u);
66       }
67     }
68     cout << articulation_point(g) << endl;
69   }
70 }