Advertisement
Korotkodul

ЗОШ конденсация debug

Jan 9th, 2022 (edited)
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.59 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. int n,m;
  30. vector <vector<int>>G;
  31. vector <vector<int>> reG;
  32. const int wh = 0, gr = 1, bl = 2;
  33. vector <int> clr;
  34. vector <int> tp;
  35.  
  36.  
  37. bool paint = 0;
  38. int cmp_num = 0;
  39.  
  40. vector <int> comp;
  41.  
  42. void dfs(int v, int pr){
  43. clr[v] = gr;
  44. if (paint) comp[v] = cmp_num;
  45. for (int u: G[v]){
  46. if (u == pr) continue;
  47. else if (clr[u] == wh){
  48. dfs(u, v);
  49. }
  50. else if (clr[u] == gr){
  51. cout<<-1<<"\n";
  52. exit(0);
  53. }
  54. }
  55. clr[v] = bl;
  56. tp.push_back(v+1);
  57. }
  58.  
  59.  
  60.  
  61.  
  62. int main()
  63. {
  64. ios::sync_with_stdio(0);
  65. cin.tie(0);
  66. cout.tie(0);
  67. cin>>n>>m;
  68. G.resize(n);
  69. clr.assign(n, wh);
  70. comp.resize(n);
  71. for (int i=0;i<m;++i){
  72. int a,b; cin>>a>>b;
  73. a--; b--;
  74. G[a].push_back(b);
  75. reG[b].push_back(a);
  76. }
  77. for (int i = 0;i<n;++i){
  78. if (clr[i] == wh){
  79. dfs(i, -1);
  80. }
  81. }
  82. reverse(tp.begin(), tp.end());
  83. cv(tp);
  84. paint = 1;
  85. for (int i=0;i<n;++i){
  86. if (clr[i] == wh){
  87. dfs(i, -1);
  88. cmp_num++;
  89. }
  90. }
  91.  
  92. }
  93.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement