Advertisement
Guest User

Untitled

a guest
Oct 10th, 2015
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <fstream>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <set>
  9.  
  10. using namespace std;
  11.  
  12. int n, m, timer;
  13. bool color[200001], ans[200001];
  14. vector <int> edge[200001];
  15. int in_t[200001], ans_t[200001];
  16.  
  17. void dfs(int cur, int parent) {
  18. int ch = 0;
  19. color[cur] = true;
  20. timer++;
  21. in_t[cur] = timer;
  22. ans_t[cur] = timer;
  23. for (int i = 0; i < edge[cur].size(); i++) {
  24. int cur_t = edge[cur][i];
  25. if (cur_t == parent) {
  26. continue;
  27. }
  28. if (!color[cur_t]) {
  29. dfs(cur_t, cur);
  30. ans_t[cur] = min(ans_t[cur], ans_t[cur_t]);
  31. if (ans_t[cur_t] >= in_t[cur]) {
  32. ans[cur] = true;
  33. }
  34. ch++;
  35. } else {
  36. ans_t[cur] = min(ans_t[cur], in_t[cur_t]);
  37. }
  38. }
  39. if (parent == -1 && ch == 1) {
  40. ans[cur] = false;
  41. }
  42. }
  43.  
  44. int main() {
  45. freopen ("points.in", "r", stdin);
  46. freopen ("points.out", "w", stdout);
  47.  
  48. cin >> n >> m;
  49.  
  50. for (int i = 0; i < m; i++) {
  51. int b, e;
  52. cin >> b >> e;
  53. b--;
  54. e--;
  55. edge[b].push_back(e);
  56. edge[e].push_back(b);
  57. }
  58.  
  59. for (int i = 0; i < m; i++) {
  60. color[i] = false;
  61. }
  62.  
  63. timer = 0;
  64. int cnt = 0;
  65.  
  66. for (int i = 0; i <= n; i++) {
  67. if (!color[i]) {
  68. dfs(i, -1);
  69. }
  70. }
  71. for (int i = 0; i <= n; i++) {
  72. if (ans[i]) {
  73. cnt++;
  74. }
  75. }
  76.  
  77. cout << cnt << endl;
  78. for (int i = 0; i <= cnt; i++) {
  79. if (ans[i]) {
  80. cout << i + 1 << endl;
  81. }
  82. }
  83.  
  84. return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement