Advertisement
Guest User

Untitled

a guest
Jan 17th, 2018
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.66 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <set>
  5. using namespace std;
  6.  
  7. const int INF = (int)1e9;
  8. const int NEUTRALMIN = INF;
  9. const int NEUTRALMAX = -INF;
  10. const int MAXN = (int)1e5;
  11. const int P = 239017;
  12. const int MOD = 1000000007;
  13.  
  14. vector < vector <int> > gg;
  15. bool used[MAXN];
  16. int tin[MAXN];
  17. int low_time[MAXN];
  18. int cur_time;
  19.  
  20. vector <int> points;
  21.  
  22. void dfs(int v, int par) {
  23. int childs = 0;
  24. used[v] = true;
  25. tin[v] = cur_time;
  26. low_time[v] = cur_time++;
  27. bool point = false;
  28.  
  29. for (int i = 0; i < (int)gg[v].size(); i++) {
  30. int to = gg[v][i];
  31. if (to == par)
  32. continue;
  33. if (!used[to]) {
  34. dfs(to, v);
  35. childs++;
  36. if (tin[v] <= low_time[to])
  37. point = true;
  38. else {
  39. low_time[v] = min(low_time[v], low_time[to]);
  40. }
  41. } else {
  42. // Found backedge
  43. low_time[v] = min(low_time[v], tin[to]);
  44. }
  45. }
  46.  
  47. if ((par == -1 && childs > 1) || (par != -1 && point)) {
  48. points.push_back(v);
  49. }
  50. }
  51.  
  52. void outputMe() {
  53. sort(points.begin(), points.end());
  54. points.resize(unique(points.begin(), points.end()) - points.begin());
  55. cout << points.size() << endl;
  56. for (int i = 0; i < (int)points.size(); i++) {
  57. cout << points[i] + 1 << " ";
  58. }
  59. }
  60.  
  61. int main() {
  62. freopen("input.txt", "r", stdin);
  63. freopen("output.txt", "w", stdout);
  64.  
  65. int n, m, st;
  66. cin >> n >> m;
  67. gg.resize(n);
  68. for (int i = 0; i < m; i++) {
  69. int a, b;
  70. cin >> a >> b;
  71. --a, --b;
  72. gg[a].push_back(b);
  73. gg[b].push_back(a);
  74. st = a;
  75. }
  76.  
  77. for (int i = 0; i < n; i++) {
  78. if (!used[i])
  79. dfs(i, -1);
  80. }
  81. outputMe();
  82.  
  83. return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement