【题意】
给出n对情侣的位置，围成环，现在需要分配食物，使得每个人都是1或2，满足任意
一对情侣间的食物不同，连着三个人的食物不能全相同。
请给出任意一种分配方案，若不存在输出-1。
【分析】
每个人相当于节点，每个节点有两种选择，然后很自然的想到了01染色，第一个约
束条件是情侣之间选择不同，即情侣之间连一条边，第二个条件是连着的三个人食
物不能全相同，也就是任意的三个节点至少有一对相邻节点不相同，所以我们把这
个圆圈的点依次连边，即（1， 2）、（3， 4），（4，5）….连边。
但是这样连边与原题中的约束条件等价吗？我们可以保证，这样连边以后跑出来的
方案一定是满足题意的，但是会不会存在出现无解的情况呢？显然，我们这样连边
每个节点的度数都为2，即整个图是由若干个环组成的，并且不存在奇数点环（同一
个环内包含若干对情侣），这样01染色肯定是存在方案的
#include<cstdio> #include<iostream> #include<cstring> #include<vector> using namespace std; const int N = 100000 + 500; int x[N * 2], y[N * 2]; vector<int> s[N * 2]; int f[N * 2]; void dfs(int x, int col) { for(int i = 0; i < s[x].size(); i++){ int y = s[x][i]; if (!f[y]){ f[y] = 3 - col; dfs(y, 3 - col); } } } int main() { int n ; scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d%d", &x[i], &y[i]); s[x[i]].push_back(y[i]); s[y[i]].push_back(x[i]); } for(int i = 1; i <= n; i++){ s[i << 1].push_back((i << 1) - 1); s[(i << 1) - 1].push_back(i << 1); } for(int i = 1; i <= 2 * n; i++) if (!f[i]) { f[i] = 1; dfs(i, 1); } for(int i = 1; i <= n; i++){ printf("%d %d\n", f[x[i]], f[y[i]]); } return 0; }