Advertisement
Guest User

Untitled

a guest
Jul 3rd, 2019
4,585
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 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 lvl [MAX_N];
  11. int dp [MAX_N];
  12.  
  13. void visit (int vertex) {
  14.   dp[vertex] = 0;
  15.   for (int nxt : adj[vertex]) {
  16.     if (lvl[nxt] == 0) { /* edge to child */
  17.       lvl[nxt] = lvl[vertex] + 1;
  18.       visit(nxt);
  19.       dp[vertex] += dp[nxt];
  20.     } else if (lvl[nxt] < lvl[vertex]) { /* edge upwards */
  21.       dp[vertex]++;
  22.     } else if (lvl[nxt] > lvl[vertex]) { /* edge downwards */
  23.       dp[vertex]--;
  24.     }
  25.   }
  26.  
  27.   /* the parent edge isn't a back-edge, subtract 1 to compensate */
  28.   dp[vertex]--;
  29.  
  30.   if (lvl[vertex] > 1 && dp[vertex] == 0) {
  31.     bridgec++;
  32.   }
  33. }
  34.  
  35. int main () {
  36.   /* problem statement: given a connected graph. calculate the number of bridges. */
  37.   ios::sync_with_stdio(false);
  38.  
  39.   int vertexc, edgec;
  40.   cin >> vertexc >> edgec;
  41.  
  42.   for (int i = 0; i < edgec; i++) {
  43.     int u, v;
  44.     cin >> u >> v;
  45.  
  46.     adj[u].push_back(v);
  47.     adj[v].push_back(u);
  48.   }
  49.  
  50.   lvl[1] = 1;
  51.   visit(1);
  52.  
  53.   cout << bridgec << endl;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement