Guest User

Untitled

a guest
Jan 23rd, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.52 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. struct edge
  8. {
  9. int to;
  10. int number;
  11. edge(int to_, int number_) : to(to_), number(number_)
  12. {}
  13. };
  14.  
  15. bool min(int a, int b)
  16. {
  17. return a < b ? a : b;
  18. }
  19.  
  20. vector<vector<edge> > edges;
  21. vector<bool> bridges;
  22. vector<int> colour;
  23. vector<int> enter;
  24. vector<int> ret;
  25. int k;
  26. int time_;
  27.  
  28. void dfs(int v, int prev_v)
  29. {
  30. cout << v << endl;
  31. colour[v] = 1;
  32. enter[v] = ++time_;
  33. ret[v] = enter[v];
  34.  
  35. int u;
  36. int number;
  37. for (size_t i = 0; i < edges[v].size(); i++)
  38. {
  39. u = edges[v][i].to;
  40. if (u == prev_v)
  41. continue;
  42.  
  43. if (colour[u] == 1)
  44. ret[v] = min(ret[v], enter[u]);
  45. else
  46. if (colour[u] == 0)
  47. {
  48. dfs(u, v);
  49. ret[v] = min(ret[v], ret[u]);
  50.  
  51. number = edges[v][i].number;
  52. if (enter[v] < ret[u]) {
  53. if (!bridges[number])
  54. k++;
  55. bridges[edges[v][i].number] = true;
  56. }
  57. }
  58. }
  59. colour[v] = 2;
  60. }
  61.  
  62. int main()
  63. {
  64. ifstream in("bridges.in");
  65. ofstream out("bridges.out");
  66.  
  67. int n, m;
  68. cin >> n >> m;
  69. edges.resize(n + 1);
  70. bridges = vector<bool>(m + 1, false);
  71. enter.resize(n + 1);
  72. ret.resize(n + 1);
  73. colour = vector<int>(n + 1, 0);
  74. k = 0;
  75. time_ = 0;
  76.  
  77. int u, v;
  78. for (int i = 1; i <= m; i++)
  79. {
  80. cin >> u >> v;
  81. edges[u].push_back(edge(v, i));
  82. edges[v].push_back(edge(u, i));
  83. }
  84.  
  85. for (int i = 1; i <= n; i++)
  86. if (colour[i] == 0)
  87. dfs(i, 0);
  88.  
  89. cout << k << '\n';
  90. for (int i = 1; i <= m; i++)
  91. if (bridges[i])
  92. cout << i << ' ';
  93. return 0;
  94. }
Add Comment
Please, Sign In to add comment