Advertisement
Guest User

Untitled

a guest
Dec 12th, 2018
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.80 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<pair<int, int> > ans;
  6. int num = 0;
  7. vector<bool> used(20000, false);
  8. int timer, tin[20000], fup[20000];
  9.  
  10. void dfs (int v, int p, vector<vector<int> >& g){
  11.     used[v] = true;
  12.     tin[v] = fup[v] = timer++;
  13.     for (int i = 0; i < g[v].size(); ++i) {
  14.         int to = g[v][i];
  15.         if (to == p)  continue;
  16.         if (used[to])
  17.             fup[v] = min (fup[v], tin[to]);
  18.         else {
  19.             dfs (to, v, g);
  20.             fup[v] = min (fup[v], fup[to]);
  21.             if (fup[to] > tin[v]){
  22.                 num++;
  23.                 ans.push_back({v, to});
  24.             }
  25.         }
  26.     }
  27. }
  28.  
  29. void find_bridges(int n, vector<vector<int> >& g){
  30.     timer = 0;
  31.     for (int i = 0; i < n; ++i)
  32.         if (!used[i])
  33.             dfs (i, -1, g);
  34. }
  35.  
  36. bool compare(pair<int, int> a, pair<int, int> b){
  37.     return(a.first == b.first && a.second == b.second || a.first == b.second && a.second == b.first);
  38. }
  39.  
  40. int main() {
  41.     int n, m, x, y;
  42.     cin >> n >> m;
  43.     vector<pair<int, int> > numbers(m);
  44.     vector<vector<int> > g(n);
  45.     vector<bool> used (n, false);
  46.     for(int i = 0; i < m; i++){
  47.         cin >> x >> y;
  48.         g[x-1].push_back(y-1);
  49.         g[y-1].push_back(x-1);
  50.         numbers[i].first = x-1;
  51.         numbers[i].second = y-1;
  52.     }
  53.  
  54.     find_bridges(n, g);
  55.  
  56.     vector<int> ans1;
  57.     for(int i = 0; i < ans.size(); i++) {
  58.         int l = 0, nu = 0;
  59.         for (int j = 0; j < m; j++)
  60.             if (compare(ans[i], numbers[j])){
  61.                 l++;
  62.                 nu = j+1;
  63.             }
  64.         if(l == 1)
  65.             ans1.push_back(nu);
  66.         else
  67.             num--;
  68.     }
  69.     cout << num << endl;
  70.     sort(ans1.begin(), ans1.end());
  71.     for(auto x : ans1)
  72.         cout << x << " ";
  73.     return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement