526互联

E. Split Into Two Sets 建模 + 染色法判奇环

发布时间 2023-09-16 15:33:35作者: Y2ZH

题意

 

给定$n$ $(2 \leq n \leq 2∗10^5)$个骨牌，第 $n$个骨牌上有 $a_i, b_i$ $(1 \leq {a_i, b_i} \leq n)$ 两个数字。

现在你需要把骨牌分成两堆，使得每一个堆里面都没有重复的数字。问是否可以实现.

 

题解

 

首先排除一些情况，一张牌上的数字不能相同，同时一个数字在所有牌上最多出现两次，否则无解。

建模过程：在每对$(a_i, b_i)$之间建一条无向边，构成一张图。每条边代表一张牌，一条边的两个端点分别代表一张牌上的两个数字。共用一个顶点的两个边应该分别属于两个集合，才不会出现重复情况。如果出现了环，环上点的个数是偶数时，有解；点的个数为奇数时，会出现一个集合中的数重复，无解。

用染色法判断奇环。

 

int n;
int flag = 0;
int cnt[maxn];
int col[maxn];
vector<int> G[maxn];
​
void dfs(int x, int fa, int c) {
    if (col[x]) {
        if (col[x] != c) flag = 1;
        return ;
    }
    col[x] = c;
    for (auto i : G[x]) {
        if (i == fa) continue;
        dfs(i, x, 3 - c);
    }
}
​
void solve() {
​
    cin >> n;
    flag = 0;
    for (int i = 1; i <= n; i ++) cnt[i] = 0, col[i] = 0, G[i].clear();
    for (int i = 1; i <= n; i ++) {
        int u, v;
        cin >> u >> v;
        if (u == v) flag = 1;
        cnt[u] ++, cnt[v] ++;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i ++) if (cnt[i] > 2) flag = 1;
    if (flag) cout << "NO\n";
    else {
        for (int i = 1; i <= n; i ++) {
            if (col[i]) continue;
            dfs(i, 0, 1);
            if (flag) {
                cout << "NO\n";
                return;
            }
        }
        cout << "YES\n";
    }
}
​