fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int nmax = 20010;
  6.  
  7. int n, m;
  8. vector < pair <int, int> > g[nmax];
  9. bool used[nmax];
  10. int tin[nmax], up[nmax], timer = 0;
  11. map < pair<int,int>, vector<int> > ans;
  12.  
  13. void dfs(int v, int p = -1)
  14. {
  15.     used[v] = 1;
  16.     tin[v] = up[v] = ++timer;
  17.     for (int i = 0; i < (int)g[v].size(); ++i)
  18.     {
  19.         int to = g[v][i].first, id = g[v][i].second;
  20.         if (to == p)
  21.             continue;
  22.         if (used[to])
  23.             up[v] = min(up[v], tin[to]);
  24.         else
  25.         {
  26.             dfs(to, v);
  27.             up[v] = min(up[v], up[to]);
  28.             if (up[to] > tin[v])
  29.             {
  30.                 bool ch = 0;
  31.                 if (v > to)
  32.                     swap(v, to), ch = 1;
  33.                 ans[make_pair(v, to)].push_back(id);
  34.                 if (ch)
  35.                     swap(v, to);
  36.             }
  37.         }
  38.     }
  39. }
  40.  
  41. int main()
  42. {
  43.     cin >> n >> m;
  44.     for (int i = 0; i < m; ++i)
  45.     {
  46.         int v, u;
  47.         cin >> v >> u;
  48.         g[v].push_back(make_pair(u, i));
  49.         g[u].push_back(make_pair(v, i));
  50.     }
  51.     for (int i = 1; i <= n; ++i)
  52.         if (!used[i])
  53.             dfs(i);
  54.     set<int> br;
  55.     for (auto i : ans)
  56.         if (i.second.size() == 1)
  57.             br.insert(*i.second.begin() + 1);
  58.     cout << (int)br.size() << "\n";
  59.     for (auto i : br)
  60.         cout << i << "\n";
  61.  
  62.     return 0;
  63. }
Success #stdin #stdout 0s 3644KB
comments (?)
stdin
copy 
6 7
1 2
2 3
3 4
1 3
4 5
4 6
5 6
stdout
copy 
1
3
https://ideone.com/YZEOQM
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!