CF741C Arpa’s overnight party and Mehrdad’s silent entering

CF741C Arpa’s overnight party and Mehrdad’s silent entering

非常简单的二分图板子，自己独立切了

观察到情侣只有两个人，分配到两个集合（两种食物），联想到二分图

显然情侣先连边

再考虑三个不能在一起

发扬人类智慧，对相邻两个，注意不要相交，也即是\(2i,2i+1\)

然后发现正好满足我们需要的要求

画个图

——|——|——|——|—

O O O O O O O O O

——— ——— ———

二分图染色应该没有人不会吧

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, a[N], b[N];
vector <int> e[N];
int col[N];
void dfs(int u, int fa) {
    if (col[u]) if (col[u] == col[fa] ^ 1) return; else cout << "-1", exit(0);
    else col[u] = col[fa] ^ 1;
    for (auto v : e[u]) if (v != fa) dfs(v, u);
}
int main() {
    cin.tie(nullptr) -> ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i], e[a[i]].emplace_back(b[i]), e[b[i]].emplace_back(a[i]);
    for (int i = 1; i <= n; i++) e[i * 2].emplace_back(i * 2 + 1), e[i * 2 + 1].emplace_back(i * 2);
    col[0] = 3;
    for (int i = 1; i <= n * 2; i++) if (!col[i]) dfs(i, 0);
    for (int i = 1; i <= n; i++) cout << col[a[i]] - 1 << ' ' << col[b[i]] - 1 << '\n';
    return 0;
}