Alex_tz307

CTC normal

Sep 11th, 2020
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.03 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector < int > G[128], GT[128], CTC[128];
  6.  
  7. int n, m, x, y, viz[128], nr;
  8. stack < int > S;
  9.  
  10. void read () {
  11.     cin >> n >> m;
  12.     while (m --) {
  13.         cin >> x >> y;
  14.         G[x].push_back (y);
  15.         GT[y].push_back (x);
  16.     }
  17. }
  18.  
  19. void DFSP (int Nod) {
  20.     viz[Nod] = 1;
  21.     for (unsigned int i = 0; i < G[Nod].size(); ++i) {
  22.         int vecin = G[Nod][i];
  23.         if (!viz[vecin]) DFSP(vecin);
  24.     }
  25.     S.push (Nod);
  26. }
  27.  
  28. void DFSM (int Nod) {
  29.     viz[Nod] = 2;
  30.     CTC[nr].push_back (Nod);
  31.     for (unsigned int i = 0; i < GT[Nod].size(); ++i) {
  32.         int vecin = GT[Nod][i];
  33.         if (viz[vecin] == 1) DFSM (vecin);
  34.     }
  35. }
  36.  
  37.  
  38. void solve () {
  39.     for (int i = 1; i <= n; ++i) if (!viz[i]) DFSP(i);
  40.     while (!S.empty()) {
  41.         int Nod = S.top();
  42.         S.pop();
  43.         if (viz[Nod] == 1) {
  44.             nr ++;
  45.             DFSM(Nod);
  46.         }
  47.     }
  48. }
  49.  
  50. void print () {
  51.  
  52. }
  53.  
  54. int main() {
  55.     read();
  56.     solve();
  57.     print();
  58.     return 0;
  59. }
  60.  
Add Comment
Please, Sign In to add comment