Advertisement
Guest User

Untitled

a guest
Apr 9th, 2020
248
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<int> ans;
  6. vector<vector<pair<int, int>>> g;
  7. vector<int> tin;
  8. vector<int> tup;
  9. int c = 1;
  10.  
  11.  
  12. void dfs(int v, int p){
  13.     tin[v] = c++;
  14.     tup[v] = tin[v];
  15.     for(auto to:g[v]){
  16.         int u = to.first;
  17.         if(u == p) continue;
  18.         if(tin[u] > 0){
  19.             tup[v] = min(tup[v], tin[u]);
  20.         }
  21.         else{
  22.             dfs(u, v);
  23.             tup[v] = min(tup[v], tup[u]);
  24.             if(tup[u] > tin[v]){
  25.                 ans.push_back(to.second);
  26.             }
  27.         }
  28.     }
  29. }
  30.  
  31. int main(){
  32.     int n, m;
  33.     cin >> n >> m;
  34.     for(int i = 0; i < n; ++i){
  35.         g.push_back({});
  36.         tup.push_back(0);
  37.         tin.push_back(0);
  38.     }
  39.     for(int i = 1; i <= m; ++i){
  40.         int u, v;
  41.         cin >> u >> v;
  42.         g[u - 1].push_back({v - 1, i});
  43.         g[v - 1].push_back({u - 1, i});
  44.     }
  45.     for(int i = 0; i < n; ++i){
  46.         if(tin[i] == 0)
  47.             dfs(i, -1);
  48.     }
  49.     sort(ans.begin(), ans.end());
  50.     cout << ans.size() << "\n";
  51.     for(int i = 0; i < ans.size(); ++i){
  52.         cout << ans[i] << "\n";
  53.     }
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement