Advertisement
Guest User

105

a guest
Mar 22nd, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <string>
  5. #include <cstdio>
  6. #include <set>
  7. #include <map>
  8. #include <sstream>
  9. #include <iterator>
  10. #include <cmath>
  11. #include <unordered_map>
  12. #include <queue>
  13.  
  14. using namespace std;
  15.  
  16. void dfs(int u, int p, int dep, vector< vector<int> > &g,
  17.          vector<int> &d, vector<int> &fup, set<pair<int, int>> &bridges){
  18.     d[u] = fup[u] = dep;
  19.     for (int i = 0; i < g[u].size(); ++i){
  20.         if(g[u][i] == p)
  21.             continue;
  22.         if(d[g[u][i]] != -1)
  23.             fup[u] = min(fup[u], d[g[u][i]]);
  24.         else{
  25.             dfs(g[u][i], u, dep + 1, g, d, fup, bridges);
  26.             fup[u] = min(fup[u], fup[g[u][i]]);
  27.             if(fup[g[u][i]] > d[u])
  28.                 bridges.insert(make_pair(u, g[u][i]));
  29.         }
  30.  
  31.     }
  32. }
  33.  
  34. int main(){
  35.     ios_base::sync_with_stdio(false);
  36.  
  37.     int n, m;
  38.     cin >> n >> m;
  39.     vector< vector<int> > g(n);
  40.     map<pair<int, int>, int> edges;
  41.     for (int i = 0; i < m; ++i){
  42.         int x, y;
  43.         cin >> x >> y;
  44.         edges[make_pair(x - 1, y - 1)] = i;
  45.         edges[make_pair(y - 1, x - 1)] = i;
  46.         g[x - 1].push_back(y - 1);
  47.         g[y - 1].push_back(x - 1);
  48.     }
  49.  
  50.     vector<int> d(n, -1);
  51.     vector<int> fup(n);
  52.     set<pair<int, int>> bridges;
  53.     for (int i = 0; i < n; ++i)
  54.         if(d[i] == -1)
  55.             dfs(i, i, 0, g, d, fup, bridges);
  56.  
  57.     vector<int> ans;
  58.     for(auto it = bridges.begin(); it != bridges.end(); ++it)
  59.         ans.push_back(edges[*it] + 1);
  60.     sort(ans.begin(), ans.end());
  61.  
  62.     cout << ans.size() << endl;
  63.     for (int i = 0; i < ans.size(); ++i)
  64.         cout << ans[i] << " ";
  65.  
  66.     cout << endl;
  67.     return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement