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
108
109
110
111
112
113
114
115
| #include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
using namespace std;
const int MAX = 1e3 + 5;
stack <int> s;
bool ok;
int n,m,t,cnt,times,scc_cnt;
int head[MAX << 1],nxt[MAX << 1],to[MAX << 1],dfn[MAX << 1],low[MAX << 1],scc[MAX << 1];
void pre ();
void build (int num1,bool ty1,int num2,bool ty2);
void _add (int u,int v);
void tarjan (int u);
int main ()
{
//freopen (".in","r",stdin);
//freopen (".out","w",stdout);
scanf ("%d",&t);
while (t--)
{
pre ();//初始化很重要
scanf ("%d%d",&n,&m);
//汉 0 满 1
for (int i = 1;i <= m;++i)
{
char da[1000],db[1000];
int a = 0,b,c = 0,d;
scanf ("%s %s",da,db);
if (da[0] == 'h') b = 0;
else b = 1;
if (db[0] == 'h') d = 0;
else d = 1;
for (int i = 1;i < strlen (da);++i) a = a * 10 + da[i] - '0';
for (int i = 1;i < strlen (db);++i) c = c * 10 + db[i] - '0';
build (a,b,c,d);
}
for (int i = 1;i <= 2 * n;++i)
if (!dfn[i]) tarjan (i);
for (int i = 1;i <= n;++i)//是否存在矛盾
{
if (scc[i] == scc[i + n])
{
ok = 0;
break;
}
}
if (ok) puts ("GOOD");
else puts ("BAD");
}
return 0;
}
void pre ()
{
cnt = times = scc_cnt = 0;
ok = 1;
init (head);init (nxt);init (to);
init (dfn);init (low);init (scc);
}
void build (int num1,bool ty1,int num2,bool ty2)//建图过程
{
if (!ty1 && !ty2)// the first one is false or the second one is false
{
_add (num1,num2 + n);// we know the first one is true so we can infer the second one is false
_add (num2,num1 + n);
}
if (!ty1 && ty2)// the first one is false or the second one is true
{
_add (num1,num2);// we know the first one is true so we can infer the second one is true
_add (num2 + n,num1 + n);
}
if (ty1 && !ty2)// the first one is true or the second one is false
{
_add (num1 + n,num2 + n);// we know the first one is false so we can infer the second one is false
_add (num2,num1);
}
if (ty1 && ty2)// the first one is true or the second one is true
{
_add (num1 + n,num2);// we know the first one is false so we can infer the second one is true
_add (num2 + n,num1);
}
}
void _add (int u,int v)//连边
{
to[++cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
}
void tarjan (int u)//强连通分量
{
dfn[u] = low[u] = ++times;
s.push (u);
for (int i = head[u];i;i = nxt[i])
{
int v = to[i];
if (!dfn[v])
{
tarjan (v);
low[u] = min (low[u],low[v]);
}
else if (!scc[v]) low[u] = min (low[u],dfn[v]);
}
if (low[u] == dfn[u])
{
++scc_cnt;
while (1)
{
int x = s.top ();
s.pop ();
scc[x] = scc_cnt;
if (x == u) break;
}
}
}
|
