Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <vector>
- #include <stack>
- #include <set>
- using namespace std;
- #define WHITE 0
- #define GRAY 1
- #define BLACK 2
- vector<vector<int>> G, Gt;
- vector<char> color;
- stack<int> S;
- vector<int> scc; int SCC = 0;
- vector<set<int>> Gscc;
- int SCCvisited = 0;
- void dfs1(int u) {
- color[u] = GRAY;
- for (int v : G[u]) if (color[v] == WHITE) dfs1(v);
- color[u] = BLACK;
- S.push(u);
- }
- void dfs2(int u) {
- scc[u] = SCC;
- color[u] = GRAY;
- for (int v : Gt[u]) {
- if (scc[v] && scc[v] != SCC) Gscc[scc[v]].insert(SCC);
- else if (color[v] == WHITE) dfs2(v);
- }
- color[u] = BLACK;
- }
- void dfs3(int U) {
- SCCvisited++;
- for (int V : Gscc[U]) {
- dfs3(V);
- return;
- }
- }
- int main() {
- #ifndef ONLINE_JUDGE
- freopen("in.txt", "r", stdin);
- #endif
- int N,M;
- scanf("%d %d", &N, &M);
- G = vector<vector<int>>(N+1);
- Gt = vector<vector<int>>(N+1);
- for (int m = 0; m < M; m++) {
- int u,v;
- scanf("%d %d", &u, &v);
- G[u].push_back(v);
- Gt[v].push_back(u);
- }
- color = vector<char>(N+1,WHITE);
- for (int u = 1; u <= N; u++) {
- if (color[u]) continue;
- dfs1(u);
- }
- color = vector<char>(N+1,WHITE);
- scc = vector<int>(N+1,0);
- Gscc = vector<set<int>>(N+1);
- while (!S.empty()) {
- int u = S.top(); S.pop();
- if (color[u]) continue;
- SCC++;
- dfs2(u);
- }
- dfs3(1);
- if (SCCvisited == SCC) printf("Bolada\n");
- else printf("Nao Bolada\n");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement