achulkov2

Untitled

Apr 12th, 2018
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.00 KB | None | 0 0
  1. //
  2. // main.cpp
  3. // 2.D
  4. //
  5. // Created by Andrey Chulkov on 7/29/15.
  6. // Copyright (c) 2015 Andrey Chulkov. All rights reserved.
  7. //
  8.  
  9. #include <iostream>
  10. #include <vector>
  11. #include <cmath>
  12. #include <map>
  13. #include <algorithm>
  14.  
  15. #define m_p make_pair
  16.  
  17. using namespace std;
  18. typedef pair<int, int> int_pair;
  19. int t = 0;
  20. vector<int> tin;
  21. vector<int> tout;
  22. vector<bool> used;
  23. vector<vector<int_pair>> graph;
  24. vector<int> points;
  25. map<pair<int, int>, int> edge_id;
  26. const int N = 1e5 + 7;
  27.  
  28. int dfs_fup(int v, int from) {
  29. int cnt = 0;
  30. bool done = false;
  31. int fup;
  32. used[v] = true;
  33. tin[v] = t;
  34. fup = tin[v];
  35. t += 1;
  36. for (auto u : graph[v]) {
  37. if (!used[u.first] && (u.second != from)) {
  38. cnt += 1;
  39. int fup_u;
  40. fup_u = dfs_fup(u.first, u.second);
  41. fup = min(fup_u, fup);
  42. if ((from != N) && (!done) && (tin[v] <= fup_u)) {
  43. points.push_back(v);
  44. done = true;
  45. }
  46. }
  47. else if (u.second != from) {
  48. fup = min(tin[u.first], fup);
  49. }
  50. }
  51. if ((from == N) && (!done) && (cnt > 1)) {
  52. points.push_back(v);
  53. }
  54. tout[v] = t;
  55. t += 1;
  56. return fup;
  57. }
  58.  
  59. int main() {
  60. int n, m;
  61. cin >> n >> m;
  62. graph.assign(n, vector<int_pair>());
  63. used.assign(n, false);
  64. tin.resize(n);
  65. tout.resize(n);
  66. for (int i = 0; i < m; i ++) {
  67. int b_i, e_i;
  68. cin >> b_i >> e_i;
  69. graph[b_i - 1].push_back(m_p(e_i - 1, i));
  70. graph[e_i - 1].push_back(m_p(b_i - 1, i));
  71. edge_id[m_p(b_i - 1, e_i - 1)] = i + 1;
  72. edge_id[m_p(e_i - 1, b_i - 1)] = i + 1;
  73. }
  74. for (int v = 0; v < n; v ++) {
  75. if (!used[v]) {
  76. dfs_fup(v, N);
  77. }
  78. }
  79. int k;
  80. k = (int) points.size();
  81. cout << k << endl;
  82. sort(points.begin(), points.end());
  83. for (int i = 0; i < k; i ++) {
  84. cout << points[i] + 1 << " ";
  85. }
  86. return 0;
  87. }
Add Comment
Please, Sign In to add comment