Advertisement
Guest User

Untitled

a guest
Mar 30th, 2020
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.50 KB | None | 0 0
  1. #include <cstdio>
  2. #include <vector>
  3. #include <stack>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8. #define WHITE 0
  9. #define GRAY  1
  10. #define BLACK 2
  11.  
  12. vector<vector<int>> G, Gt;
  13. vector<char> color;
  14. stack<int> S;
  15. vector<int> scc; int SCC = 0;
  16. vector<set<int>> Gscc;
  17. int SCCvisited = 0;
  18.  
  19. void dfs1(int u) {
  20.   color[u] = GRAY;
  21.   for (int v : G[u]) if (color[v] == WHITE) dfs1(v);
  22.   color[u] = BLACK;
  23.   S.push(u);
  24. }
  25.  
  26. void dfs2(int u) {
  27.   scc[u] = SCC;
  28.   color[u] = GRAY;
  29.   for (int v : Gt[u]) {
  30.     if (scc[v] && scc[v] != SCC)  Gscc[scc[v]].insert(SCC);
  31.     else if (color[v] == WHITE)   dfs2(v);
  32.   }
  33.   color[u] = BLACK;
  34. }
  35.  
  36. void dfs3(int U) {
  37.   SCCvisited++;
  38.   for (int V : Gscc[U]) {
  39.     dfs3(V);
  40.     return;
  41.   }
  42. }
  43.  
  44. int main() {
  45.  
  46. #ifndef ONLINE_JUDGE
  47.   freopen("in.txt", "r", stdin);
  48. #endif
  49.  
  50.   int N,M;
  51.   scanf("%d %d", &N, &M);
  52.   G = vector<vector<int>>(N+1);
  53.   Gt = vector<vector<int>>(N+1);
  54.   for (int m = 0; m < M; m++) {
  55.     int u,v;
  56.     scanf("%d %d", &u, &v);
  57.     G[u].push_back(v);
  58.     Gt[v].push_back(u);
  59.   }
  60.  
  61.   color = vector<char>(N+1,WHITE);
  62.   for (int u = 1; u <= N; u++) {
  63.     if (color[u]) continue;
  64.     dfs1(u);
  65.   }
  66.  
  67.   color = vector<char>(N+1,WHITE);
  68.   scc = vector<int>(N+1,0);
  69.   Gscc = vector<set<int>>(N+1);
  70.   while (!S.empty()) {
  71.     int u = S.top(); S.pop();
  72.     if (color[u]) continue;
  73.     SCC++;
  74.     dfs2(u);
  75.   }
  76.  
  77.   dfs3(1);
  78.   if (SCCvisited == SCC)  printf("Bolada\n");
  79.   else                    printf("Nao Bolada\n");
  80.  
  81.   return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement