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
| #include <cstdio> #include <stack> #include <algorithm>
const int MAXN = 105; const int MAXM = 1005; struct Edge; struct Node { Edge *e; int dfn, low, belong; bool inq; } N[MAXN << 1]; struct Edge { Node *u, *v; Edge *next; Edge(Node *u, Node *v) : u(u), v(v), next(u->e) {} }; void addEdge(int u, int v) { #ifdef DBG printf("edge : %d --> %d\n", u, v); #endif N[u].e = new Edge(&N[u], &N[v]); } void clearGraph(int n) { for (int i = 1; i <= n; i++) { for (Edge *&e = N[i].e, *next; e; next = e->next, delete e, e = next); N[i].low = N[i].dfn = N[i].belong = 0; N[i].inq = false; } } int getV(int x, int k) { return (x << 1) - k; } struct twoSat { std::stack<Node *> s; int dfsClock, sccCnt; void tarjan(Node *u) { s.push(u); u->inq = true; u->dfn = u->low = ++dfsClock; for (Edge *e = u->e; e; e = e->next) { if (e->v->dfn == 0) { tarjan(e->v); u->low = std::min(u->low, e->v->low); } else if (e->v->inq) u->low = std::min(u->low, e->v->dfn); } if (u->dfn == u->low) { Node *c; sccCnt++; while (true) { c = s.top(); s.pop(); c->belong = sccCnt; c->inq = false; if (c == u) break; } } } bool check(int n) { for (int i = 1; i <= n; i++) if (N[getV(i, 0)].belong == N[getV(i, 1)].belong) return false; return true; } bool operator()(int n) { dfsClock = sccCnt = 0; while (!s.empty()) s.pop(); for (int i = 1; i <= n << 1; i++) if (N[i].dfn == 0) tarjan(&N[i]); #ifdef DBG printf("sccCnt = %d\n", sccCnt); #endif return check(n); } } ts; int parseInt(char *s) { int res = 0; for (char *p = s; *p; p++) res = res * 10 + *p - '0'; return res; } int main() { int T; scanf("%d", &T); while (T--) { int n, m; scanf("%d %d", &n, &m); clearGraph(n << 1); for (int i = 1; i <= m; i++) { char kx[5], ky[5]; int x, y, xv, yv; scanf("%s", kx); x = parseInt(kx + 1); scanf("%s", ky); y = parseInt(ky + 1); xv = kx[0] == 'm'; yv = ky[0] == 'm'; addEdge(getV(x, xv ^ 1), getV(y, yv)); addEdge(getV(y, yv ^ 1), getV(x, xv)); } puts(ts(n) ? "GOOD" : "BAD"); } return 0; }
|