Rentib

Untitled

Feb 16th, 2020
143
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.87 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. vector<pair<int, int>> G[500007];
  4. int pre[500007], low[500007], nr, liczba_mostow;
  5. bool w[500007], most[1000007];
  6. void DFS(int a, int p = -1, int to = 0, int k = 0){
  7. w[a] = 1;
  8. pre[a] = low[a] = ++nr;
  9. for(auto i : G[a]){
  10. tie(to, k) = i;
  11. if(to == p) continue;
  12. if(w[to]) low[a] = min(low[a], pre[to]);
  13. else{
  14. DFS(to, a);
  15. low[a] = min(low[a], low[to]);
  16. if(low[to] > pre[a] && !most[k]){
  17. most[k] = 1;
  18. liczba_mostow++;
  19. }
  20. }
  21. }
  22. }
  23. int main(){
  24. ios_base::sync_with_stdio(0);
  25. cin.tie(0);
  26. int n, m;
  27. cin >> n >> m;
  28. for(int i = 0, a, b;i < m;i++){
  29. cin >> a >> b;
  30. G[a].emplace_back(b, i + 1);
  31. G[b].emplace_back(a, i + 1);
  32. }
  33. DFS(1);
  34. cout << liczba_mostow << '\n';
  35. for(int i = 1;i <= m;i++)
  36. if(most[i])
  37. cout << i << ' ';
  38. }
Advertisement
Add Comment
Please, Sign In to add comment