Advertisement
Guest User

Untitled

a guest
Mar 23rd, 2019
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.82 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdio.h>
  3.  
  4. vector <int> t_1;
  5. vector <int> t_2;
  6. int time_ = 0;
  7.  
  8. int dfs(int v, vector <vector <int>> &g, vector <int> &visited, int count)
  9. {
  10. int p = -1;
  11. visited[v] = 1; //vertex has visited
  12.  
  13. t_1[v] = t_2[v] = time_++;
  14.  
  15. for (int i = 0; i < g[v].size(); i++)
  16. {
  17. int cur = /*...*/; //current vertex
  18.  
  19. if (cur == p) continue;
  20.  
  21. if (visited[cur]) t_2[v] = min(t_2[v], t_1[cur]);
  22.  
  23. else
  24. {
  25. dfs_rec(cur, g, visited, count);
  26. t_2[v] = min(t_2[v], t_2[cur]);
  27.  
  28. if (t_1[v] < t_2[cur]) count++;
  29. }
  30. }
  31.  
  32. return count;
  33. }
  34.  
  35. void dfs(int v, vector <vector <int>> &g, vector <int> &visited, int count)
  36. {
  37. int p = -1;
  38. visited[v] = 1; //vertex has visited
  39.  
  40. t_1[v] = t_2[v] = time_++;
  41.  
  42. for (int i = 0; i < g[v].size(); i++)
  43. {
  44. int cur = /*...*/; //current vertex
  45.  
  46. if (cur == p) continue;
  47.  
  48. if (visited[cur]) t_2[v] = min(t_2[v], t_1[cur]);
  49.  
  50. else
  51. {
  52. dfs(cur, g, visited, count);
  53. t_2[v] = min(t_2[v], t_2[cur]);
  54. }
  55. }
  56. }
  57.  
  58. int main()
  59. {
  60. vector <vector <int>> g;
  61. vector <int> visited; //1 - visited, 0 - not visited;
  62.  
  63. int n, m;
  64. cin >> n; //vertexes
  65. cin >> m; //edges
  66.  
  67. g.resize(n);
  68. visited.resize(n);
  69. t_1.resize(n);
  70. t_2.resize(n);
  71.  
  72. int u, v, count = 0;
  73.  
  74. for (int i = 0; i < m; i++)
  75. {
  76. cin >> u; //v_1
  77. cin >> v; //v_2
  78.  
  79. g[u].push_back(v);
  80. g[v].push_back(u);
  81. }
  82.  
  83. for (int i = 0; i < n; i++) visited[i] = 0;
  84.  
  85. for (int i = 0; i < n; i++)
  86. {
  87. if (visited[i] == 0)
  88. dfs(i, g, visited, count);
  89. }
  90.  
  91. cout << count;
  92.  
  93. return 0;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement