Advertisement
Guest User

Untitled

a guest
Mar 31st, 2020
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.46 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8. long long inf = 1e9;
  9.  
  10. int n, m;
  11. vector < vector < int > > g;
  12. vector < bool > used;
  13. vector < int > tin, f;
  14. set <int> dots;
  15. int timer = 0;
  16.  
  17. void dfs_find_points(int v, int par = -1) {
  18. used[v] = true;
  19. tin[v] = timer;
  20. timer++;
  21. f[v] = tin[v];
  22.  
  23. int cntDfs = 0;
  24.  
  25. for (int i = 0; i < g[v].size(); i++) {
  26. int to = g[v][i];
  27. if (to == par) {
  28. continue;
  29. }
  30. if (used[to])
  31. f[v] = min(f[v], tin[to]);
  32. else
  33. {
  34. dfs_find_points(to, v);
  35. cntDfs++;
  36. f[v] = min(f[v], f[to]);
  37.  
  38. if (f[to] >= tin[v] && par != -1) {
  39. dots.insert(v);
  40. }
  41. }
  42. }
  43.  
  44. if (par == -1 && cntDfs > 1) {
  45. dots.insert(v);
  46. }
  47. }
  48.  
  49.  
  50.  
  51. int main() {
  52. cin >> n >> m;
  53. g.assign(n, vector <int>());
  54. used.assign(n, false);
  55. tin.assign(n, inf);
  56. f.assign(n, inf);
  57.  
  58. for (int i = 0; i < m; i++) {
  59. int x, y;
  60. cin >> x >> y;
  61. x--;
  62. y--;
  63. g[x].push_back(y);
  64. g[y].push_back(x);
  65. }
  66.  
  67. for (int i = 0; i < n; i++) {
  68. if (used[i] == false) {
  69. dfs_find_points(i, -1);
  70. }
  71. }
  72.  
  73. cout << dots.size() << "\n";
  74.  
  75. for (auto e : dots) {
  76. cout << e + 1 << "\n";
  77. }
  78.  
  79. system("pause");
  80. return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement