Advertisement
Guest User

Untitled

a guest
Jul 3rd, 2019
2,098
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. const int MAX_N = 300005;
  7.  
  8. int bridgec;
  9. vector<int> adj [MAX_N];
  10. int dfs [MAX_N];
  11. int low [MAX_N];
  12. int cur;
  13.  
  14. void visit (int vertex, int parent) {
  15.   cur++;
  16.   dfs[vertex] = cur;
  17.   low[vertex] = cur;
  18.  
  19.   for (int nxt : adj[vertex]) {
  20.     if (dfs[nxt] == 0) {
  21.       visit(nxt, vertex);
  22.       low[vertex] = min(low[vertex], low[nxt]);
  23.       if (low[nxt] > dfs[vertex]) {
  24.         bridgec++;
  25.       }
  26.     } else if (nxt != parent) {
  27.       low[vertex] = min(low[vertex], dfs[nxt]);
  28.     }
  29.   }
  30. }
  31.  
  32. int main () {
  33.   /* problem statement: given a connected graph. calculate the number of bridges. */
  34.   ios::sync_with_stdio(false);
  35.  
  36.   int vertexc, edgec;
  37.   cin >> vertexc >> edgec;
  38.  
  39.   for (int i = 0; i < edgec; i++) {
  40.     int u, v;
  41.     cin >> u >> v;
  42.  
  43.     adj[u].push_back(v);
  44.     adj[v].push_back(u);
  45.   }
  46.  
  47.   visit(1, 0);
  48.  
  49.   cout << bridgec << endl;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement