Uva 10765 - Doves and bombs

  1  /*
  2  Problem link
  3  Type: Graph - Find articulation points
  4  Algorithm:
  5      || Articulation points - bridge (undirected graph):
  6      - Articulation points are vertexs in graph G whose deletion will
  7      cause the graph to disconnect (increase in connected components)
  8      - Bridges are edges in graph G whose deletion will cause the graph
  9      toe disconnect (increase in connected components)
 10  
 11      || Find articulation points - bridge
 12      - We can use DFS to find articulation points - bridges in
 13      O(V + E) time complexity.
 14  
 15      - dfs_num[u]: the index of u in the DFS tree, is assigned to u
 16      when u is first met in the DFS tree.
 17  
 18      - dfs_low[u]: the lowest index in the DFS tree that u can reach,
 19      when u is first met, dfs_low[u] = dfs_num[u], the algorithm will
 20      update dfs_low[u].
 21  
 22      - fa[u]: the parent of u in the DFS tree (the vertex whose we came
 23      from to reach u).
 24  
 25      - For each vertex u in the DFS tree, check for its neighbor vertex v:
 26       + If v is not visited (dfs_num[v] = 0) then we run DFS for v, after the
 27      recursion, update dfs_low[u] with dfs_low[v]. After this update, if
 28      dfs_low[v] >= dfs_low[u] then u is an articulation point
 29      dfs_low[v] > dfs_low[u] then u v is a bridge
 30       + If v is visited (u v is a back-edge), check whether u v is not a
 31      direct cycle (you come to v from u, now you are at v and you
 32      are not going back to u), that is, v != fa[u], we update dfs_low[u]
 33      with dfs_num[v].
 34  
 35      - Explanation: v is indexed after u in the DFS tree, this mean
 36      dfs_num[v] > dfs_num[u], but if we travel from v and reach a
 37      vertex that indexed smaller than u (ancestor of u) without
 38      going through u, we have dfs_low[v] < dfs_num[u]. This implies
 39      that even when we remove vertex u, there is still another way for
 40      v to go to some vertex w ancestor of u. Therefore, u is not an articulation
 41      point => u is an articulation point when dfs_low[v] >= dfs_num[u].
 42  
 43      The explanation for bridge is almost the same.
 44  
 45      - One trivial case where we have to fix for this algorithm is when
 46      u is a root of DFS tree. In this case, u is an articulation point
 47      when it has more than 1 children.
 48  
 49      || In this problem:
 50      - I use an array called deltaInc[u] in this problem, this array
 51      represents the number of connected components will increase after
 52      we delete u.
 53      - For each vertex in G (articulation or not), calculate the number
 54      of connected components after we remove this vertex. Sort the result
 55      and print out the first m elements.
 56  */
 57  #include <iostream>
 58  #include <cstdio>
 59  #include <cstring>
 60  #include <cmath>
 61  #include <vector>
 62  #include <cstdlib>
 63  #include <algorithm>
 64  
 65  using namespace std;
 66  const int maxn = 10010;
 67  
 68  class Vertex {
 69  public:
 70      int id;
 71      vector<int> adjList;
 72  };
 73  
 74  class ArticulationPoint {
 75  public:
 76      int id, point;
 77  
 78      ArticulationPoint(int _id, int _p): id(_id), point(_p) {}
 79  
 80      bool operator<(const ArticulationPoint &p) const {
 81          if (this->point < p.point) return true;
 82          else if (this->point == p.point && this->id > p.id) return true;
 83          return false;
 84      }
 85  
 86      bool operator>(const ArticulationPoint &p) const {
 87          if (this->point > p.point) return true;
 88          else if (this->point == p.point && this->id < p.id) return true;
 89          return false;
 90      }
 91  };
 92  
 93  bool readFile();
 94  void articulationPoint();
 95  void solve();
 96  
 97  vector<Vertex> vlist;
 98  vector<ArticulationPoint> result;
 99  int dfs_low[maxn], dfs_num[maxn], fa[maxn], deltaInc[maxn];
100  int n, m, dfsCnt, nChild, root;
101  
102  int main()
103  {
104      while (readFile()) {
105          solve();
106      }
107      return 0;
108  }
109  
110  bool readFile() {
111      cin >> n >> m;
112      if (n == 0 && m == 0) return false;
113      vlist.assign(n, Vertex());
114  
115      int u, v;
116      cin >> u >> v;
117      while (u != -1 && v != -1) {
118          vlist[u].adjList.push_back(v);
119          vlist[v].adjList.push_back(u);
120  
121          cin >> u >> v;
122      }
123  
124      return true;
125  }
126  
127  void articulationPoint(int u) {
128      dfs_num[u] = dfs_low[u] = ++dfsCnt;
129  
130      for (int i = 0; i < (int)vlist[u].adjList.size(); i++) {
131          int v = vlist[u].adjList[i];
132          if (dfs_num[v] == 0) {
133              fa[v] = u;
134              if (u == root) nChild++;
135  
136              articulationPoint(v);
137              if (dfs_low[v] >= dfs_num[u])
138                  deltaInc[u]++;
139  
140              dfs_low[u] = min(dfs_low[u], dfs_low[v]);
141          } else if (v != fa[u])
142              dfs_low[u] = min(dfs_low[u], dfs_num[v]);
143      }
144  }
145  
146  void solve() {
147      result.clear();
148      int cc = 0;
149      for (int i = 0; i < n; i++) {
150          dfs_low[i] = dfs_num[i] = 0;
151          deltaInc[i] = 0;
152          fa[i] = i;
153      }
154  
155      for (int i = 0; i < n; i++) {
156          if (dfs_num[i] == 0) {
157              dfsCnt = 0;
158              cc++;
159              root = i;
160              nChild = 0;
161              articulationPoint(i);
162              deltaInc[i] = nChild - 1;
163          }
164      }
165  
166      for (int i = 0; i < n; i++) {
167          result.push_back(ArticulationPoint(i, cc + deltaInc[i]));
168      }
169  
170      sort(result.begin(), result.end(), greater<ArticulationPoint>());
171  
172      for (int i = 0; i < m; i++)
173          cout << result[i].id << " " << result[i].point << endl;
174      cout << endl;
175  }