ChickyHas @ 2023-09-19 09:50:43
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int N = 201;
int t, n, m, dfn[N], low[N], s[N], top, cnt, res[N], idx;
vector<int> e[N];
string s1, s2;
bool b[N];
void Tarjan(int x) {
dfn[x] = low[x] = ++idx;
s[++top] = x, b[x] = 1;
for (int i : e[x]) {
if (!dfn[i]) {
Tarjan(i);
low[x] = min(low[x], low[i]);
} else if (b[i]) {
low[x] = min(low[x], dfn[i]);
}
}
if (low[x] == dfn[x]) {
++cnt;
while (s[top + 1] != x) {
b[s[top]] = 0, res[s[top--]] = cnt;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> t;
while (t--) {
cin >> n >> m;
top = cnt = idx = 0;
for (int i = 1; i <= n << 1; ++i) {
s[i] = dfn[i] = low[i] = b[i] = res[i] = 0;
e[i].clear();
}
for (int i = 1; i <= m; ++i) {
cin >> s1 >> s2;
bool b1 = s1[0] == 'm', b2 = s2[0] == 'm';
int x = 0, y = 0;
for (int j = 1; j < s1.size(); ++j) {
x = (x << 3) + (x << 1) + s1[j] - '0';
}
for (int j = 1; j < s2.size(); ++j) {
y = (y << 3) + (y << 1) + s2[j] - '0';
}
if (b1 && b2) {
e[x + n].emplace_back(y);
e[y + n].emplace_back(x);
} else if (!b1 && b2) {
e[x].emplace_back(y);
e[y + n].emplace_back(x + n);
} else if (b1 && !b2) {
e[x + n].emplace_back(y);
e[y].emplace_back(x);
} else {
e[x].emplace_back(y + n);
e[y].emplace_back(x + n);
}
}
for (int i = 1; i <= n << 1; ++i) {
if (!dfn[i]) {
Tarjan(i);
}
}
bool f = 1;
for (int i = 1; i <= n; ++i) {
if (res[i] == res[i + n]) {
f = 0;
break;
}
}
cout << (f ? "GOOD\n" : "BAD\n");
}
return 0;
}
rt,不知道哪里错了
by ChickyHas @ 2023-09-19 09:57:30
md,建图建错了,真难绷