并查集

总概

  1. 合并两个集合
  2. 查询某个节点的祖宗的节点
    • 记录每个集合的大小：（绑定到根节点）
    • 每个节点到根节点的距离：（绑定到每个节点上）

1250. 格子游戏

题目链接：

1250. 格子游戏

题解思路：

根据题目，将各个元素映射到一维数组中，连接起来，检查连接的过程中是否出现环（若出现环状-》出现连接的时候两个节点在同一个连通块中）就说明有圈了

题目代码：

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
#include <bits/stdc++.h>

using namespace std;

const int N = 41000;
int p[N];
int n, m;
int get(int x, int y){
    return x * n + y;
    //如果是第二种初始化的话可以按照数据来乘倍率
    /*
    return x * 200 + y;
    */
}

int find(int x){
    if(p[x] != x) p[x] = find(p[x]); //只有根节点的p[x] == x，所以继续找
    return p[x];
}

int main ()
{
    
    cin >> n >> m;
    int res = 0;
    for(int i = 0; i < n * n; i++) p[i] = i; //初始化
    /*
    从头初始化到结尾,第二种初始化
    for(int i = 1; i < N; i++)p[i] = i;
    */
    for(int i = 1; i <= m; i++){
        int x, y;
        char d;
        cin >> x >> y >> d;
        int a, b;
        //因为输入原因(初始化原因)以及get函数x,y需要从0开始，如果按第二种初始化就不用，也可以不用从0开始
        x--, y--;   
        a = get(x, y);
        if(d == 'D') b = get(x + 1, y);
        else b = get(x, y + 1);
        int pa = find(a), pb = find(b); 
        if(pa == pb){       //父亲节点相等就说明在同一个连通块中，连线必定有环
            res = i; break;
        }
        p[pa] = pb;
    }
    if(!res)cout << "draw" << endl;
    else cout << res << endl;
    return 0;
}

1252. 搭配购买

题目链接：

1252. 搭配购买 - AcWing题库

题解思路：

思路：根据题目，将各个搭配连接起来，就相当于各个连通块选择，使得总价为vol，价值最大的01背包问题

题目代码：

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
/*
思路：根据题目，将各个搭配连接起来，就相当于各个连通块选择，使得总价为vol，价值最大的01背包问题
*/


#include <bits/stdc++.h>

using namespace std;
const int N = 10010;
int v[N], w[N], p[N], f[N];         // v[N] —— 价格、w[N] —— 价值、f[N] —— dp
int n, m, vol;

int find(int x){
    if(p[x] != x) p[x] = find(p[x]); // 祖宗节点的p[x] == x,持续向上查找到祖宗节点
    return p[x];
}

int main ()
{
    cin >> n >> m >> vol;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i++) p[i] = i;
    while(m --){
        int a, b;
        cin >> a >> b;
        int pa = find(a), pb = find(b);
        if(pa != pb){
            v[pb] += v[pa]; //总价格全部绑定到祖宗节点上去
            w[pb] += w[pa]; //总价值全部绑定到祖宗节点上去
            p[pa] = p[pb];  //pa的祖宗是pb
        }
    }
    
    // 01背包问题
    for(int i = 1; i <= n; i++){
        if(p[i] == i) //如果是祖宗节点，才进行状态转移（只有祖宗节点是这个连通块的总量）
            for(int j = vol; j >= v[i]; j--){
                f[j] = max(f[j], f[j - v[i]] + w[i]);  //状态转移
            }
    }
    cout << f[vol] << endl;
    return 0;
}

237. 程序自动分析

题目链接：

237. 程序自动分析

题解思路：

离散化+并查集

因为i,j的范围是1~1e9,所以需要离散化，然后就是基本的，相等的点连接到一个连通图里面，不相等的点进行判断。

离散化：

  1. 保序：排序+判重+二分
  2. 不保序： map、hash表

此题不保序

题目代码：

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
/*
因为i,j的范围是1~1e9,所以需要离散化，然后就是基本的，相等的点连接到一个连通图里面，不相等的点进行判断。
*/


#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int n, m, p[N];
unordered_map<int, int> mp; //散列表
struct Q{
    int x, y, e;
}q[N];

int find(int x){
    if(p[x] != x)p[x] = find(p[x]);
    return p[x];
}

//离散化
int get(int x){
    if(mp.count(x) == 0) mp[x] = ++n; 
    return mp[x]; //返回离散化后对应的值
}

int main ()
{
    int T;
    cin >> T;
    while(T--){
        cin >> m;
        n = 0;
        mp.clear();
        
        //离散化各个点
        for(int i = 1; i <= m; i++ ){
            int x, y, e;
            cin >> x >> y >> e;
            q[i] = {get(x), get(y), e};
        }
        
        //初始化
        for(int i = 1; i <= n; i++) p[i] = i;
        
        //处理相等的值，将相等的值连接到一个连通块
        for(int i = 1; i <= m; i++){
            if(q[i].e == 1){
                //cout << q[i].x << " " << q[i].y << endl;
                int pa = find(q[i].x), pb = find(q[i].y);
                p[pa] = pb;
            }
        }
        int flag = 0;
        
        //非相等的值判断是否在同一个连通块中
        for(int i = 1; i <= m; i++){
            if(q[i].e == 0){
                int pa = find(q[i].x), pb = find(q[i].y);
                if(pa == pb) {
                    flag = 1;
                    break;
                }
            }
        }
        if(flag)cout << "NO" << endl;
        else cout << "YES" << endl;
    }
    return 0;
}

238. 银河英雄传说

题目链接：

238. 银河英雄传说

题解思路：

并查集：统一维护每个战舰到排头战舰的距离

当我们询问两个战舰间隔的时候是，|dx - dy| - 1 or 0(特判)

  1. 让排头当根节点->同时维护一个size表示当前队列的长度
  2. 假设有一个初始的队列a,新加一个队列b，就把队列b的排头d[b]+size[a]，并且在find函数里面刷新后面所有d[x];
  3. d[x]表示的是x到p[x]的距离，这样就可以很方便的算出每个节点到最排头的距离

题目代码：

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
#include <bits/stdc++.h>

using namespace std;
const int N = 30010;
int p[N], d[N], Size[N], T;

int find(int x){
    if(p[x] != x){
        int root = find(p[x]);  //持续向上找到根节点
        d[x] += d[p[x]];        //会更新当前节点到根节点的距离
        p[x] = root;            //向上找到根节点
    }
    return p[x];
}

int main ()
{
    cin >> T;
    //初始化
    for(int i = 1; i < N; i++) p[i] = i, Size[i] = 1;
    while(T--){
        char op;
        int a, b;
        cin >> op >> a >> b;
        if(op == 'M'){
            int pa = find(a), pb = find(b);
            d[pa] = Size[pb];       //距离pb的距离
            Size[pb] += Size[pa];   //将a这一列的大小加到b这一列
            p[pa] = pb;             //pa的父节点是pb
        }else{
            int pa = find(a), pb = find(b);
            if(pa != pb){           //不在同一列
                cout << "-1" << endl;
            }else{                  //在同一列
                if(a != b)          //不是同一个节点
                    cout << abs(d[a] - d[b]) - 1 << endl;
                else cout << 0 << endl;
            }
            
        }
    }
}

239. 奇偶游戏

题目链接：

239. 奇偶游戏

题解思路：

总思想：前缀和

前缀和思想，如果是[l, r]内有奇数个1的话那么必有S[r] - S[l-1]为奇数，也即是S[r]、S[l - 1]奇偶性不同

同理如果是[l, r]内有偶数个1的话那么必有S[r] - S[l-1]为偶数，也即是S[r]、S[l - 1]奇偶性相同

方法一（扩展域）

枚举思想：

  1. 假设这个节点a是偶，并添加一个节点是a+M是奇
  2. 奇偶性相同的放在同一个集合中去
  3. 如果一组数据中，类型是偶数，就判断 a与b+M在不在同一个集合中
    • 在同一个集合中说明矛盾
    • 不在同一个集合中说明不矛盾
  4. 如果一组数据中，类型是奇数，就判断a与b是否在同一个集合中
    • 在同一个集合中说明，矛盾
    • 不在同一个集合中说明不矛盾

方法二（带边权）

维护一个带边权的并查集

  1. d[x]表示x与p[x]的关系
    • 0表示同类
    • 1表示不同类
  2. x与y是同类
    • p[x] = p[y]
      • d[x] ^ d[y]是0无矛盾，d[x]^d[y]是1有矛盾
    • p[x] != p[y]
      • d[p[x]] = d[x] ^ d[y]
  3. xy异类
    • p[x] = p[y]
      • d[x] ^ d[y]是0有矛盾，d[x]^d[y]是1无矛盾
    • p[x] != p[y]
      • d[p[x]] = d[x] ^ d[y] ^ 1
  4. 综上所述，就相当于代边权一个路径d表示x与根节点的关系，在find函数中需要对d进行更新类似于238题

题目代码：

方法一 （扩展域）

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
#include <bits/stdc++.h>

using namespace std;
const int N = 41000, M = N / 2;
int p[N], n, m;
unordered_map<int, int> mp;

int find(int x){
    if(p[x] != x)p[x] = find(p[x]);
    return p[x];
}

//离散化
int get(int x){
    if(mp.count(x) == 0) mp[x] = ++n;
    return mp[x];
}

int main ()
{
    cin >> n >> m;
    n = 0;
    
    //初始化
    for(int i = 0; i < N; i++) p[i] = i;
    
    int res = m;
    for(int i = 1; i <= m; i++){
        string t;   //类型（奇偶）
        int a, b;
        cin >> a >> b >> t; 
        a = get(a - 1), b = get(b);     //相当于奇偶性~（Sl-1, Sr）
        if(t == "even"){                //奇偶性相同
            if(find(a) == find(b + M)){ //必然b+M与a的奇偶性就不能相同
                res = i - 1;            
                break;
            } 
            p[find(a)] = find(b);
            p[find(a + M)] = find(b + M);
        }else{                          //奇偶性不同
            if(find(a) == find(b)){     //那么奇偶性必然不能相同
                res = i - 1;
                break;
            }
            p[find(a)] = find(b + M);   //奇偶性相同的点加入到同一个集合中
            p[find(a + M)] = find(b);
        }
    }
    cout << res << endl;
    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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>

using namespace std;
const int N = 41000, M = N / 2;
int p[N], d[N], n, m;
unordered_map<int, int> mp;

int find(int x){
    if(p[x] != x){
        int root = find(p[x]);
        d[x] += d[p[x]] % 2; //奇偶性原因，不影像最后结果，同时也防止爆int
        p[x] = root;
    }
    return p[x];
}

//离散化
int get(int x){
    if(mp.count(x) == 0) mp[x] = ++n;
    return mp[x];
}

int main ()
{
    cin >> n >> m;
    n = 0;
    
    //初始化
    for(int i = 0; i < N; i++) p[i] = i;
    
    int res = m;
    for(int i = 1; i <= m; i++){
        string t;   //类型（奇偶）
        int a, b;
        cin >> a >> b >> t; 
        a = get(a - 1), b = get(b);     //相当于奇偶性~（Sl-1, Sr）
        if(t == "even"){                //奇偶性相同
            int pa = find(a), pb = find(b);
            if(pa == pb){               //在同一集合中
                if((d[a] ^ d[b]) % 2){  //防止爆int
                    res = i - 1;
                    break;
                }
            }
            else{
                p[pa] = pb;
                d[pa] = d[a] ^ d[b];
            }
        }else{                              //奇偶性不同
            int pa = find(a), pb = find(b);
            if(pa == pb){                   //在同一集合中
                if((d[a] ^ d[b]) % 2 == 0){ //防止爆int
                    res = i - 1;
                    break;
                }
            }
            else{
                p[pa] = pb;
                d[pa] = d[a] ^ d[b] ^ 1;
            }
        }
    }
    cout << res << endl;
    return 0;
}