Advertisement
Guest User

Untitled

a guest
Nov 12th, 2019
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.87 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <fstream>
  3.  
  4. using namespace std;
  5.  
  6. vector < vector <int> > g, num;
  7. vector <int> used, tin, tup;
  8. set <int> ans, ans2;
  9.  
  10. int timer = 0;
  11. void dfs(int v, int predok, int nomer){
  12.     timer++;
  13.     used[v] = 1;
  14.     tin[v] = timer;
  15.     tup[v] = timer;
  16.     for (int i = 0; i < g[v].size(); i++){
  17.         int to = g[v][i];
  18.         if (used[to] == 0){
  19.             dfs(to, v, num[v][i]);
  20.             tup[v] = min(tup[v], tup[to]);
  21.         }
  22.         else if (nomer != num[v][i]){
  23.             tup[v] = min(tup[v], tin[to]);
  24.         }
  25. //            if (check.count({predok, i}) > 1 || check.count({i, predok}) > 1){
  26. //                nr = -15;
  27. //            }
  28.     }
  29.     if (tup[v] > tin[predok] && predok != -1){
  30.         ans.insert(nomer);
  31.     }
  32. }
  33.  
  34. void dfs2(int v){
  35.     used[v] = 1;
  36.     for (int i = 0; i < g[v].size(); i++){
  37.         int to = g[v][i];
  38.         if (used[to] == 0){
  39.             if (ans.count(num[v][i]) && num[v][i] != - 1){
  40.                 //cout << num[v][i] << endl;
  41.                 ans2.insert(num[v][i]);
  42.             }
  43.             dfs2(to);
  44.         }
  45.     }
  46. }
  47.  
  48. int main(){
  49.    // freopen("bridges.in", "r", stdin);
  50.    // freopen("bridges.out", "w", stdout);
  51.     int n, m, x, y;
  52.     cin >> n >> m;
  53.     g.resize(n);
  54.     used.resize(n, 0);
  55.     tin.resize(n);
  56.     tup.resize(n);
  57.     num.resize(n);
  58.     for (int i = 0; i < m; i++){
  59.         cin >> x >> y;
  60.         x--;
  61.         y--;
  62.         g[x].push_back(y);
  63.         g[y].push_back(x);
  64.         num[x].push_back(i + 1);
  65.         num[y].push_back(i + 1);
  66. //        check.insert({x, y});
  67. //        check.insert({y, x});
  68.     }
  69.     //cout<<"input correct"<<endl;
  70.     dfs(0, -1, -1);
  71.     used.assign(n, 0);
  72.     dfs2(0);
  73.     cout << ans2.size() << endl;
  74.     for (set<int>::iterator it = ans2.begin(); it != ans2.end(); ++it) {
  75.         cout << *it << " ";
  76.     }
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement