Advertisement
Korotkodul

ЗОШ точки сочленения ОК

Jan 9th, 2022
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.62 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #define pii pair <int,int>
  11. using namespace std;
  12. using ll = long long;
  13. using ld = long double;
  14. void cv(vector <int> &v){
  15. for (auto x: v) cout<<x<<' ';
  16. cout<<"\n";
  17. }
  18.  
  19. void cvl(vector <ll> &v){
  20. for (auto x: v) cout<<x<<' ';
  21. cout<<"\n";
  22. }
  23.  
  24.  
  25. void cvv(vector <vector <int> > &v){
  26. for (auto x: v) cv(x);
  27. cout<<"\n";
  28. }
  29.  
  30. struct edge{
  31. int fr, to, id;
  32. };
  33. int n,m;
  34. vector <vector <edge> > G;
  35. const int bl = 2, gr = 1, wh = 0, inf = 2e9;
  36. vector <int> clr;
  37.  
  38. void she(edge x){
  39. cout<<x.fr+1<<' '<<x.to+1<<' '<<x.id<<"\n";
  40. }
  41.  
  42. void shG(){
  43. for (int i=0;i<n;++i){
  44. cout<<"i = "<<i<<"\n";
  45. for (int j = 0; j <G[i].size();++j){she(G[i][j]);}
  46. cout<<"\n\n";
  47. }
  48. }
  49. int curT = 0;
  50. set <int> pnt;//точки сочлен
  51. vector <int> tIn, tUp;
  52.  
  53. void dfs(int v, int parId){//parId - id ребра по которомц пришли в v
  54. clr[v] = gr;
  55. tIn[v] = curT++;
  56. int kol = 0;
  57. if (parId == -1) kol--;
  58. for (auto e: G[v]){
  59. if (e.id == parId) continue;
  60. else if (clr[e.to] == wh){
  61. dfs(e.to, e.id);
  62. tUp[v] = min(tUp[v], tUp[e.to]);
  63. if (tIn[v] <= tUp[e.to]){
  64. kol++;
  65. }
  66. if (kol > 0){
  67. pnt.insert(e.fr);
  68. }
  69. }
  70. else if (clr[e.to] == gr){
  71. tUp[v] = min(tUp[v], tIn[e.to]);
  72. }
  73. }
  74. clr[v] = bl;
  75. }
  76.  
  77.  
  78. int main()
  79. {
  80. ios::sync_with_stdio(0);
  81. cin.tie(0);
  82. cout.tie(0);
  83. cin>>n>>m;
  84. G.resize(n);
  85. clr.assign(n, wh);
  86. tIn.assign(n, inf);
  87. tUp.assign(n, inf);
  88. int id = 0;
  89. for (int i=0;i<m;++i){
  90. int a,b;
  91. cin>>a>>b;
  92. if (a>b) swap(a,b);
  93. a--; b--;
  94. edge any;
  95. any = {a, b, id};
  96. G[a].push_back(any);
  97. any = {b, a, id};
  98. G[b].push_back(any);
  99. id++;
  100. }
  101. //shG();
  102. for (int i = 0; i < n;++i){
  103. if (clr[i] == wh){
  104. dfs(i, -1);
  105. }
  106. }
  107. cout<<pnt.size()<<"\n";
  108. //sort(pnt.begin(), pnt.end());
  109. for (int i: pnt) cout<<i+1<<"\n";
  110.  
  111. }
  112. /*
  113. 13 17
  114. 1 2
  115. 2 3
  116. 4 5
  117. 2 6
  118. 2 7
  119. 8 9
  120. 1 3
  121. 1 4
  122. 1 5
  123. 6 7
  124. 3 8
  125. 3 9
  126. 10 11
  127. 11 12
  128. 11 12
  129. 10 13
  130. 10 1
  131. 7
  132. 1
  133. 1
  134. 2
  135. 3
  136. 10
  137. 10
  138. 11
  139. */
  140.  
  141.  
  142.  
  143. /*
  144. 13 17
  145. 1 2
  146. 2 3
  147. 4 5
  148. 2 6
  149. 2 7
  150. 8 9
  151. 1 3
  152. 1 4
  153. 1 5
  154. 6 7
  155. 3 8
  156. 3 9
  157. 10 11
  158. 11 12
  159. 11 12
  160. 10 13
  161. 10 1
  162.  
  163. 10 13
  164. 1 2
  165. 2 3
  166. 4 5
  167. 2 6
  168. 2 7
  169. 8 9
  170. 1 3
  171. 1 4
  172. 1 5
  173. 6 7
  174. 3 8
  175. 3 9
  176. 9 10
  177.  
  178. 9 12
  179. 1 2
  180. 2 3
  181. 4 5
  182. 2 6
  183. 2 7
  184. 8 9
  185. 1 3
  186. 1 4
  187. 1 5
  188. 6 7
  189. 3 8
  190. 3 9
  191. */
  192.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement