Advertisement
Um_nik

Untitled

Mar 22nd, 2014
226
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.38 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. const int N = (int)1e5 + 10;
  9.  
  10. struct Edge
  11. {
  12. int to, ind;
  13. Edge () {}
  14. Edge (int to, int ind) : to(to), ind(ind) {}
  15. };
  16. vector <Edge> g[N];
  17. vector <int> ans;
  18. int tin[N];
  19. int d[N];
  20. bool used[N];
  21. int tme = 0;
  22.  
  23. void dfs(int v, int par = -1)
  24. {
  25. used[v] = 1;
  26. tin[v] = tme++;
  27. d[v] = tin[v];
  28. bool isPar = false;
  29. int cntChild = 0;
  30. int minVal = (int)1e9;
  31. for (int i = 0; i < (int)g[v].size(); i++)
  32. {
  33. int to = g[v][i].to;
  34. if (!used[to])
  35. {
  36. cntChild++;
  37. dfs(to, v);
  38. d[v] = min(d[v], d[to]);
  39. minVal = min(minVal, d[to]);
  40. }
  41. else
  42. {
  43. if ((to == par && isPar) || to != par)
  44. {
  45. d[v] = min(d[v], tin[to]);
  46. }
  47. if (to == par)
  48. isPar = true;
  49. }
  50. }
  51. if (par == -1 && cntChild > 1)
  52. ans.push_back(v);
  53. else if (par != -1 && minVal >= tin[v])
  54. ans.push_back(v);
  55. }
  56.  
  57. int main()
  58. {
  59.  
  60. int n, m;
  61. scanf("%d%d", &n, &m);
  62.  
  63. for (int i = 0; i < m; i++)
  64. {
  65. int a, b;
  66. scanf("%d%d", &a, &b);
  67. g[a].push_back(Edge(b, i + 1));
  68. g[b].push_back(Edge(a, i + 1));
  69. }
  70.  
  71. for (int i = 1; i <= n; i++)
  72. {
  73. if (!used[i])
  74. dfs(i);
  75. }
  76. sort(ans.begin(), ans.end());
  77. printf("%d\n", (int)ans.size());
  78. for (int i = 0; i < (int)ans.size(); i++)
  79. printf("%d ", ans[i]);
  80.  
  81. return 0;
  82. }
  83. /*
  84. 9 12
  85. 1 2 1 3
  86.  
  87. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement