运用生成树+二分图进行构造：26暑杭电多校 4-02

1002 B. Binary Choice

我们发现，题目已经规定了每种颜色的数量为偶数，但却没有规定每种值的数量为偶数。

但每种值的数量必须为偶数。所以我们可以先思考一下，在不理分组的情况下，是否存在一种办法每种值的个数为偶数。

一个很常见的转化是给 ai,bia_i,b_i 连边，然后让每个点的度数为偶数。

现在转化为一个图论问题。

图论问题涉及边的构造，一般用生成树。

我们随便考虑一个连通块。首先连通块边的数量必须为偶数。

我们再随便考虑一棵dfs生成树。非树边我们随便定向。定完后对于树上的节点，从叶子开始，逐步定树边。现在由每个点的奇偶性就可以决定其往上那条边的方向性。

由于连通块总边数为偶数，所以其他点定完后根节点也必然满足。

由此，我们就设计了一种方案，使每种值的数量为偶数。

image-20260801102729663

接下来要进行分组。

我们可以大胆猜测只要值和颜色的数量为偶数，那么必然存在一种合法分组。不然这题就很难做下去。

我们考虑如果两个点有相同值或相同颜色，就连一条边。同时每个点只连一条值边，一条颜色边。

然后对所有点黑白染色。满足每条边必然是一个白点和一个黑点相连。

我们发现连边后因为是值边和颜色边交替，所以所有环的长度都为偶数。所以必然构成一个二分图。

所以必然可以黑白染色。

image-20260801103106098

总得来说，像这种限制越多，越难下手的构造题，其实构造的多样性是最多的。不要把限制看的太死，不一定必然为唯一构造。

涉及图论的构造，学会用生成树+二分图这两个技巧。

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 200010
struct node {
	int a, b, c; 
}a[N];
int n, m, i, j, k, T;
vector<int>ans1, ans2; 

void Init() {
	ans1.clear(); ans1.resize(n + 1); 
	ans2.clear(); ans2.resize(n + 1); 
	unordered_map<int, int>mp; 
	for(i = 1, k = 0; i <= n; ++i) {
		if(!mp[a[i].a]) mp[a[i].a] = ++k; 
		if(!mp[a[i].b]) mp[a[i].b] = ++k; 
		a[i].a = mp[a[i].a]; a[i].b = mp[a[i].b]; 
	}
	mp.clear(); 
	for(i = 1, k = 0; i <= n; ++i) {
		if(!mp[a[i].c]) mp[a[i].c] = ++k; 
		a[i].c = mp[a[i].c]; 
	}
}

namespace Sol1 {
	vector<vector<pair<int, int> > >G, son; 
	vector<int>vis, c, b, f, cnt;  
	int i, j, k; 
	void init() {
		G.clear(); G.resize(2 * n + 10); 
		b.clear(); b.resize(2 * n + 10); 
		c.clear(); c.resize(2 * n + 10); 
		vis.clear(); vis.resize(2 * n + 10); 
		son.clear(); son.resize(2 * n + 10); 
		cnt.clear(); cnt.resize(2 * n + 10); 
		f.resize(2 * n + 10); 
		for(i = 1; i <= 2 * n; ++i) f[i] = i;  
	}
	int fa(int x) {
		if(f[x] == x) return x; 
		return f[x] = fa(f[x]);  
	}
	void cun(int x, int y, int i) {
		G[x].pb({y, i}); G[y].pb({x, i}); 
		f[fa(x)] = fa(y); 
	}
	void dfs1(int x) {
		vis[x] = 1; 
		for(auto t : G[x]) 
			if(!vis[t.fi]) {
				son[x].pb(t);  
				dfs1(t.fi); b[t.se] = 1; 
			}
	}
	void dfs2(int x) {
		for(auto t : son[x]) {
			int y, i = t.se; 
			dfs2(y = t.fi); 
			if(c[y] & 1) {
				c[y] ^= 1; 
				if(a[i].a == y) ans1[i] = 0; 
				else ans1[i] = 1; 
			}
			else {
				c[x] ^= 1; 
				if(a[i].a == x) ans1[i] = 0; 
				else ans1[i] = 1; 
			}
		}
	}
	int main() {
		init(); 
		for(i = 1; i <= n; ++i) 
			cun(a[i].a, a[i].b, i); 
		for(i = 1; i <= n; ++i) ++cnt[fa(a[i].a)]; 
		for(i = 1; i <= 2 * n; ++i) 
			if(fa(i) == i) {
				if(cnt[i] & 1) return -1; 
				dfs1(i); 
			}
		for(i = 1; i <= n; ++i) 
			if(!b[i]) {
				c[a[i].a] ^= 1; ans1[i] = 0; 
			}
		for(i = 1; i <= 2 * n; ++i) 
			if(fa(i) == i) {
				dfs2(i); 
			}
		return 0; 
	}
}

namespace Sol2 {
	int i, j, k; 
	vector<vector<int> >G; 
	vector<int>vis;  
	void init() {
		G.clear(); G.resize(2 * n + 1); 
		vis.clear(); vis.resize(2 * n + 1); 
	}
	void dfs(int x) {
		vis[x] = 1; 
		for(int y : G[x]) 
			if(!vis[y]) {
				ans2[y] = (ans2[x] ^ 1);  
				dfs(y); 
			}
	}
	void cun(int x, int y) {
		G[x].pb(y); G[y].pb(x); 
	}
	void main() {
		init(); 
		map<int, int>mp; 
		for(i = 1; i <= n; ++i) {
			if(ans1[i]) swap(a[i].a, a[i].b); 
			if(!mp[a[i].a]) mp[a[i].a] = i; 
			else cun(mp[a[i].a], i), mp[a[i].a] = 0;  
		}
		mp.clear(); 
		for(i = 1; i <= n; ++i) {
			if(!mp[a[i].c]) mp[a[i].c] = i; 
			else cun(mp[a[i].c], i), mp[a[i].c] = 0;  
		}
		for(i = 1; i <= n; ++i)
			if(!vis[i]) {
				dfs(i); 
			}
	}
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
	T = read();
	while(T--) {
		n = read(); int ret = 0; 
		for(i = 1; i <= n; ++i) {
			a[i].a = read(); a[i].b = read(); a[i].c = read(); 
		} 
		Init(); 
		ret = Sol1 :: main(); 
		if(ret == -1) { printf("-1\n"); continue; }
		Sol2 :: main(); 
		for(i = 1; i <= n; ++i) printf("%d", ans1[i]); printf("\n"); 
		for(i = 1; i <= n; ++i) printf("%d", ans2[i]); printf("\n"); 
	}

	return 0;
}