Advertisement
haufont

Untitled

Sep 4th, 2016
3,445
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<set>
  5. #include<map>
  6. #include<fstream>
  7.  
  8. using namespace std;
  9.  
  10. const int maxn = 300113;
  11. vector<int> gr[maxn];
  12. bool used[maxn];
  13. int tin[maxn];
  14. int fup[maxn];
  15. int times = 0;
  16.  
  17. map<pair<int, int>, int> d;
  18. map<pair<int, int>, int> kratnrebro;
  19. vector<pair<int, int>> qw;
  20.  
  21. ifstream in("bridges.in");
  22. ofstream out("bridges.out");
  23.  
  24. #define mp make_pair
  25. //#define in cin
  26. //#define out cout
  27.  
  28. void dfs(int v, int p = -1)
  29. {
  30.     used[v] = 1;
  31.     tin[v] = fup[v] = times++;
  32.     for (int i = 0; i < gr[v].size(); i++)
  33.     {
  34.         int to = gr[v][i];
  35.         if (to == p) continue;
  36.         if (used[to])
  37.         {
  38.             fup[v] = min(fup[v], tin[to]);
  39.         }
  40.         else
  41.         {
  42.             dfs(to, v);
  43.             fup[v] = min(fup[v], fup[to]);
  44.             if (fup[to] > tin[v] && kratnrebro[mp(v, to)] == 1)
  45.             {
  46.                 pair<int, int> outr = mp(v, to);
  47.                 qw.push_back(outr);
  48.             }
  49.         }
  50.     }
  51. }
  52.  
  53. int main()
  54. {
  55.     int n, m;
  56.     in >> n >> m;
  57.     int ap, bp;
  58.     for (int i = 0; i < m; i++)
  59.     {
  60.         in >> ap >> bp;
  61.         gr[ap].push_back(bp);
  62.         gr[bp].push_back(ap);
  63.         d[mp(ap, bp)] = i + 1;
  64.         d[mp(bp, ap)] = i + 1;
  65.         kratnrebro[mp(ap, bp)] += 1;
  66.         kratnrebro[mp(bp, ap)] += 1;
  67.     }
  68.     for (int i = 1; i <= n; i++)
  69.     {
  70.         if (!used[i])
  71.         {
  72.             dfs(i);
  73.         }
  74.     }
  75.     out << qw.size() << endl;
  76.     for (int i = 0; i < qw.size(); i++)
  77.     {
  78.         out << d[mp(qw[i].first, qw[i].second)] << " ";
  79.     }
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement