Advertisement
Guest User

Untitled

a guest
Jan 26th, 2020
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.55 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <unordered_map>
  6.  
  7. using namespace std;
  8.  
  9. #include <cstdio>
  10. struct Edge {
  11. int from;
  12. int to;
  13. int number;
  14. };
  15. vector <Edge> edges[20002];
  16.  
  17. vector<int> wow;
  18. int timee = 0;
  19. int tin[20002];
  20. int dp[20002];
  21. int used[20002];
  22. vector <Edge> ans;
  23.  
  24.  
  25.  
  26. void dfs(int v, Edge kill_me)
  27. {
  28. int parent = kill_me.to;
  29.  
  30. used[v] = 1;
  31. tin[v] = dp[v] = timee++;
  32. for (auto e : edges[v]) {
  33. if (e.to == parent) continue;
  34. if (used[e.to] == 1)
  35. dp[v] = min(dp[v], tin[e.to]);
  36. else {
  37. dfs(e.to, e);
  38. dp[v] = min(dp[v], dp[e.to]);
  39. if (dp[e.to] > tin[v])
  40. ans.push_back(kill_me);
  41. }
  42. }
  43. }
  44.  
  45.  
  46. int main()
  47. {
  48. int n, m;
  49. cin >> n >> m;
  50. for (int i = 1; i <= m; ++i)
  51. {
  52. int u, v; cin >> u >> v;
  53. Edge e;
  54. e.from = u; e.to = v; e.number = i;
  55. edges[u].push_back(e);
  56. e.from = v; e.to = u; e.number = i;
  57. edges[v].push_back(e);
  58. }
  59. timee = 0;
  60. Edge weird; weird.to = 100000; weird.from = 2000000; weird.number = -1;
  61. for (int i = 1; i <= n; ++i)
  62. if (used[i] == 0)
  63. dfs(i, weird);
  64. cout <<"size = " << ans.size() << '\n';
  65.  
  66. int array[ans.size()];
  67. for (int i = 0; i < ans.size(); ++i) {
  68. array[i] = ans[i].number;
  69. }
  70. sort(array, array + ans.size());
  71. for (int i = 0; i < ans.size(); ++i) {
  72. cout << array[i] << '\n';
  73. }
  74. return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement