Advertisement
Korotkodul

ЗОШ мосты A debug

Jan 9th, 2022 (edited)
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.38 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<<' '<<x.to<<' '<<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. vector <edge> bridge; //id мостов
  51. stack <int> comp;
  52. vector <int> tIn, tUp;
  53.  
  54. void dfs(int v, int parId){//parId - id ребра по которомц пришли в v
  55. clr[v] = gr;
  56. tIn[v] = curT++;
  57. comp.push(v);
  58. cout<<"v = "<<v<<"\n";
  59. cout<<"clr\n";
  60. cv(clr);
  61.  
  62. cout<<"tIn\n";
  63. cv(tIn);
  64. cout<<"tUp\n";
  65. cv(tUp);
  66. for (auto e: G[v]){
  67. if (e.id == parId) continue;
  68. else if (clr[e.to] == wh){
  69. dfs(e.to, e.id);
  70. tUp[v] = min(tUp[v], tUp[e.to]);
  71. if (tUp[e.to] >= tIn[e.to]){
  72. bridge.push_back(e);
  73. }
  74. }
  75. else if(clr[e.to] == gr){
  76. tUp[v] = min(tUp[v], tIn[e.to]);
  77. }
  78.  
  79. }
  80. clr[v] = bl;
  81. }
  82.  
  83.  
  84.  
  85. int main()
  86. {
  87. ios::sync_with_stdio(0);
  88. cin.tie(0);
  89. cout.tie(0);
  90. cin>>n>>m;
  91. G.resize(n);
  92. clr.assign(n, wh);
  93. tIn.assign(n, inf);
  94. tUp.assign(n, inf);
  95. int id = 0;
  96. for (int i=0;i<m;++i){
  97. int a,b;
  98. cin>>a>>b;
  99. if (a>b) swap(a,b);
  100. a--; b--;
  101. edge any;
  102. any = {a, b, id};
  103. G[a].push_back(any);
  104. any = {b, a, id};
  105. G[b].push_back(any);
  106. id++;
  107. }
  108. //shG();
  109. for (int i = 0; i < n;++i){
  110. if (clr[i] == wh){
  111. dfs(i, -1);
  112. }
  113. }
  114. cout<<"ANSWER\n";
  115. cout<<bridge.size()<<"\n";
  116. for (auto i: bridge){
  117. cout<<i.id+1<<"\n";
  118. }
  119. cout<<"clr\n"; cv(clr);
  120. }
  121. /*
  122. 6 7
  123. 1 2
  124. 2 3
  125. 3 4
  126. 1 3
  127. 4 5
  128. 4 6
  129. 5 6
  130.  
  131. */
  132.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement