Advertisement
Guest User

Untitled

a guest
Apr 30th, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. std::vector<std::vector<std::pair<int, int>>> a;
  6. std::vector<int> tin, bridges;
  7. int timer = 0;
  8.  
  9. int dfs(int i, int prev) {
  10.     if (tin[i] != 0)
  11.         return tin[i];
  12.     ++timer;
  13.     tin[i] = timer;
  14.     int tmp_time = tin[i];
  15.     for (auto x : a[i])
  16.         if (x.first != prev) {
  17.             int t = dfs(x.first, i);
  18.             if (t > tin[i])
  19.                 bridges.push_back(x.second);
  20.             tmp_time = std::min(t, tmp_time);
  21.         }
  22.     tin[i] = tmp_time;
  23.     return tmp_time;
  24. }
  25.  
  26. int main() {
  27.     int n, m;
  28.     std::cin >> n >> m;
  29.     a.resize(n);
  30.     tin.resize(n, 0);
  31.     for (int i = 1; i != m + 1; ++i) {
  32.         int x, y;
  33.         std::cin >> x >> y;
  34.         --x;
  35.         --y;
  36.         a[x].push_back(std::make_pair(y, i));
  37.         a[y].push_back(std::make_pair(x, i));
  38.     }
  39.  
  40.     for (int i = 0; i != n; ++i)
  41.         if (tin[i] == 0)
  42.             dfs(i, -1);
  43.  
  44.     sort(bridges.begin(), bridges.end());
  45.     std::cout << bridges.size() << std::endl;
  46.     for (auto x : bridges)
  47.         std::cout << x << " ";
  48.     system("pause");
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement