种类并查集

        
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

        #include <bits/stdc++.h>
using namespace std;

// 并查集判二分图：把每个点拆成"本体"和"对立面"，矛盾即非二分图
struct DSU {
    using T = int;

    vector<T> fa;  // fa[x] 为 x 的父节点
    vector<T> sz;  // sz[x] 为集合大小（仅根节点有效）

    DSU(int n = 0) {
        init(n);
    }

    void init(int n) {
        fa.resize(n + 1);
        sz.assign(n + 1, 1);
        iota(fa.begin(), fa.end(), 0);
    }

    // 查询 x 所在集合的根（路径压缩）
    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }

    // x 与 y 是否在同一集合
    bool same(int x, int y) {
        return find(x) == find(y);
    }

    // 合并 x 与 y 所在集合（按大小合并）
    void unite(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx == fy) return;

        if (sz[fx] < sz[fy]) swap(fx, fy);
        fa[fy] = fx;
        sz[fx] += sz[fy];
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    // 拆点：i 表示点 i，i+n 表示"点 i 的对立面"
    DSU dsu(2 * n);
    auto enemy = [n](int x) {
        return x + n;
    };

    bool ok = true;
    while (m--) {
        int x, y;
        cin >> x >> y;

        // x 与 y 必须在不同类别中。
        if (dsu.same(x, y)) {
            ok = false;
        }
        dsu.unite(x, enemy(y));
        dsu.unite(enemy(x), y);
    }

    cout << (ok ? "YES" : "NO") << "\n";
    return 0;
}
    

        
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

        #include <bits/stdc++.h>
using namespace std;

// 种类并查集（并查集判二分图）竞赛精简版：每个点拆成 x 与 x+n（对立面）
// 输入 n m 与 m 条边 x y（x 与 y 必须不同类），输出 YES/NO
// 口诀：要求不同类，就把 x 挂到 y 的对立面、y 挂到 x 的对立面
// 易错点：拆点后容量翻倍，init 要开到 2n；x 与 y 同集合才是矛盾，合并本身不会矛盾
// 和别的模板一起用时 maxn 只留一份

const int maxn = 1e6 + 5;
int fa[maxn * 2], sz[maxn * 2];  // 拆点后下标 1..2n

void init(int n) {
    for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
}

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

// 小树挂大树
void unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    if (sz[fx] < sz[fy]) swap(fx, fy);
    fa[fy] = fx;
    sz[fx] += sz[fy];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    init(2 * n);  // 拆点：i 是点 i，i+n 是它的对立面
    bool ok = true;
    while (m--) {
        int x, y;
        cin >> x >> y;
        if (find(x) == find(y)) ok = false;  // 同类却要求不同类：矛盾
        unite(x, y + n);  // x 和 y 的对立面同类
        unite(x + n, y);  // x 的对立面和 y 同类
    }
    cout << (ok ? "YES" : "NO") << "\n";
    return 0;
}