1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
| #include <bits/stdc++.h> #define pb push_back #define fi first #define se second using namespace std; using pii = pair<int, int>; const int N = 1e5 + 5, M = 405; vector<int> G[N], DAG[N]; vector<pii> edges; int n, m, _; int dfn[N], num[N], low[N], id, tot, sta[N], top, deg[N], idx[N]; bool in[N]; int vis[N], spe[N]; bitset<N> bit[M]; void tarjan(int u) { in[u] = 1; low[u] = dfn[u] = ++id; sta[++top] = u; for(int v : G[u]) { if(!dfn[v]) { tarjan(v); low[u] = min(low[u],low[v]); } else if(in[v]) low[u] = min(low[u],dfn[v]); } if(low[u]==dfn[u]) { tot++; while(top) { int tmp = sta[top--]; in[tmp] = 0; num[tmp] = tot; if(tmp==u) break; } } } void dfs(int u, int t) { if(spe[u]) { bit[t] |= bit[spe[u]]; return; } vis[u] = t; bit[t].set(u); for(int v : DAG[u]) { if(vis[v]==t) continue; dfs(v, t); } } void prework() { for(int i=1; i<=n; i++) if(!dfn[i]) tarjan(i); for(auto it : edges) { int u = num[it.fi], v = num[it.se]; if(u!=v) DAG[u].pb(v), deg[u]++, deg[v]++; } int lim = (int)sqrt(tot) + 1; iota(idx+1, idx+tot+1, 1); sort(idx+1, idx+tot+1, [](int x, int y) { return deg[x] > deg[y]; }); for(int i=1; i<=lim; i++) { dfs(idx[i], i); spe[idx[i]] = i; } } bool dfs2(int s, int t, int tt) { if(s==t) return 1; if(spe[s]) return bit[spe[s]].test(t); vis[s] = tt; for(int ss : DAG[s]) { if(vis[ss]==tt) continue; if(dfs2(ss, t, tt)) return 1; } return 0; } void solve(int t) { int u, v; scanf("%d%d", &u, &v); ++u, ++v; if(num[u]==num[v]) puts("Good"); else puts((dfs2(num[u], num[v], t) ? "Good" : "Bad")); } int main() { scanf("%d%d", &n, &m); for(int i=1; i<=m; i++) { int u, v; scanf("%d%d", &u, &v); ++u, ++v; G[u].pb(v); edges.emplace_back(u, v); } prework(); scanf("%d", &_); for(int i=1; i<=_; i++) solve(400+i); return 0; }
|