发表更新数据结构与算法16 分钟读完 (大约2469个字)

并查集拓展

边带权

银河英雄传说

有 $T$ 条指令，每条指令格式为以下两种之一：

  1. $M-i-j$，表示让第 $i$ 号战舰所在列的全部战舰保持原有顺序，接在第 $j$ 号战舰所在列的尾部。

  2. $C-i-j$，表示询问第 $i$ 号战舰与第 $j$ 号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。

数据范围：$N≤30000, T≤500000$

Solution

维护数组 $dp$ 表示 $i$ 到 $root$ 的距离，那么查询的答案便是 $abs(dp[a] - dp[b]) - 1$。

当 $a$ 向 $b$ 连一条边时，有 $fa[a] = b$，此时根结点 $a$ 的深度会增加 $b$ 的集合大小，因此我们需要一个 $sz$ 数组维护集合大小。

同时在进行路径压缩时，对于未更新的结点也要一同更新深度。

Code

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;

int dp[N], sz[N], fa[N];

int find (int x) {
    if (x != fa[x]) {
        int root = find(fa[x]);
        dp[x] += dp[fa[x]];
        fa[x] = root;
    }
    return fa[x];
}

int main()
{
    int t, a, b;
    string s;
    cin >> t;
    for (int i = 1; i <= 30000; i++) {
        dp[i] = 0;
        sz[i] = 1;
        fa[i] = i;
    }
    while (t--) {
        cin >> s >> a >> b;
        int pa = find(a), pb = find(b);
        if (s == "M") {
            if (pa != pb) {
                fa[pa] = pb;
                dp[pa] = sz[pb];
                sz[pb] += sz[pa];
            }
        } else {
            if (pa != pb) cout << -1 << endl;
            else cout << max(abs(dp[a] - dp[b]) - 1, 0) << endl;
        }
    }
    return 0;
}

拓展域

食物链

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。

  1. $1-X-Y$，表示 $X$ 和 $Y$ 是同类。

  2. $2-X-Y$，表示 $X$ 吃 $Y$。

判断有多少句假话。$(1≤N≤50000,0≤K≤100000)$

Solution

$1-n$ 表示动物 $i$ 的同类，$n+1-2n$ 表示动物 $i$ 的猎物，$2n+1 - 3n$ 表示动物 $i$ 的天敌。

对于操作1: 查询 $x$ 和 $y$ 的天敌域，猎物域是不是在一个集合，是则累加答案，否则进行合并。

对于操作2: 查询 $x$ 和 $y$ 的同类域，猎物域是不是在一个集合，是则累加答案，否则进行合并。

Code

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

int fa[1000005];

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

void join (int a, int b) {
    a = find(a), b = find(b);
    if (a != b) fa[a] = b;
}

int main()
{
    int n, k, a, b, c, res = 0;
    cin >> n >> k;
    for (int i = 1;  i <= n * 3; i++) fa[i] = i;
    while (k--) {
        cin >> c >> a >> b;
        if (a > n || b > n) {
            res++;
            continue;
        }
        if (c == 1) {
            if (find(a) == find(b + n) || find(a) == find(b + 2 * n)) {
                res++;
                continue;
            }
            else {
                /// a和b是同类，a和b的猎物也是同类，a和b的天敌也是同类
                join(a, b);
                join(a + n, b + n);
                join(a + 2 * n, b + 2 * n);
            }
        } else {
            if (a == b || find(a) == find(b) || find(a) == find(b + n)) {
                res++;
                continue;
            }
            else {
                /// a的猎物是b， b的天敌是a，b的猎物是a的天敌
                join(a, b + 2 * n);
                join(a + n, b);
                join(a + 2 * n, b + n);
            }
        }
    }
    cout << res << endl;
    return 0;
}

奇偶游戏

给你 $m$ 个询问，每一个询问给出一个区间的左右端点和区间中的 $1$ 的数量的奇偶性，输出不出现矛盾的最大的 $k$ 值，即 $1-k$ 无矛盾，$1- k + 1$ 矛盾。$(N≤10^9,M≤10000)$

Solution1（边带权）

  1. 我们可以用 $sum$ 数组表示序列 S 的前缀和,那么会得到以下性质.

$s[l~r]$ 有偶数个 $1$，等价于 $sum[l-1]$ 与 $sum[r]$ 奇偶性相同 $(1+0=1,0+0=0,1是奇数,0是偶数)$
$s[l~r]$ 有奇数个 $1$，等价于 $sum[l-1]$ 与 $sum[r]$ 奇偶性不同 $(1+1=0,0+1=0,1是奇数,0是偶数)$

  1. 根据传递性，可以使用边带权，边权 $d[x] = 0$，表示 $x$ 与 $f[x]$ 的奇偶性相同; 为 $1$，表示 $x$ 与 $fa[x]$ 的奇偶性不同,在路径压缩的过程中,对 $x$ 到树根路径的所有边权做异或$(xor)$。

  2. 对于每个问题, 设离散化后 $l - 1$ 和 $r$ 的值分别是 $x$ 和 $y$ , 设 $c$ 表示当前问题的回答($c = 0$ 表示偶数个, $c = 1$ 表示奇数个)

若 $x$ 和 $y$ 在一个集合中, 直接判断 $d[x] xor d[y]$ 是否等于 $c$，若不等于,则矛盾，直接输出结果。

若 $x$ 和 $y$ 不在一个集合中，说明无法判断，此时合并两个集合，得到俩个的树根 $p$ 和 $q$, $d[x]$ 与 $d[y]$ 分别表示 $x - p$ 与 $y - q$ 之间所有边权的 “xor” 和，$p - q$ 之间的边权为 $d[p]$, 显然, 路径 $x - y$ 由 $x - p$, $p - q$, $q - y$ 组成，所以 $x$ 与 $y$ 的奇偶性关系 $c = d[x] (xor) d[y] (xor) d[p]$，得到 $d[p] = d[x] (xor) d[y] (xor) c$。

Code

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

int fa[N], d[N];
unordered_map<int, int> mp;
vector<int> g;

struct Node {
    int a, b, c;
} q[N];

int find (int x) {
    if (x != fa[x]) {
        int root = find(fa[x]);
        d[x] ^= d[fa[x]];
        fa[x] = root;
    }
    return fa[x];
}

int main()
{
    int L, n, a, b, pa, pb;
    string s;
    cin >> L >> n;
    for (int i = 1; i <= n; i++) {
        cin >> q[i].a >> q[i].b >> s;
        if (s[0] == 'e') q[i].c = 0;
        else q[i].c = 1;
        g.push_back(q[i].a - 1);
        g.push_back(q[i].b);
    }
    sort(g.begin(), g.end());
    g.erase(unique(g.begin(), g.end()), g.end());
    for (int i = 1; i <= (int)g.size(); i++) {
        fa[i] = i;
        mp[g[i - 1]] = i;
        d[i] = 0;
    }
    int i = 1;
    for (; i <= n; i++) {
        a = mp[q[i].a - 1], b = mp[q[i].b];
        pa = find(a), pb = find(b);
        if (pa != pb) {
            fa[pa] = pb;
            d[pa] ^= d[a] ^ d[b] ^ q[i].c;
        } else {
            if (d[a] ^ d[b] != q[i].c) break;
        }
    }
    cout << i - 1 << endl;
    return 0;
}

Solution2（拓展域）

$1 - n$ 表示 $sum[i]$ 为奇，$n + 1 - 2 * n$ 表示 $sum[i]$ 为偶。

当查询区间为奇数时：判断 $a$ 的奇数域是否与 $b$ 的奇数域同在一个集合，是则矛盾，否则合并 $a$ 的奇数域与 $b$ 的偶数域，$a$ 的偶数域与 $b$ 的奇数域。

当查询区间为偶数时：判断 $a$ 的奇数域是否与 $b$ 的偶数域同在一个集合，是则矛盾，否则合并 $a,b$ 的奇数域和偶数域。

Code

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

int fa[N];
vector<int> g;
unordered_map<int, int> mp;

struct Node {
    int a, b, c;
} q[N];

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

void join (int x, int y) {
    x = find(x), y = find(y);
    if (x != y) fa[x] = y;
} 

int main()
{
    int L, m, n, a, b;
    string s;
    cin >> L >> m;
    for (int i = 1; i <= m; i++) {
        cin >> q[i].a >> q[i].b >> s;
        if (s == "even") q[i].c = 0;
        else q[i].c = 1;
        g.push_back(q[i].a - 1);
        g.push_back(q[i].b);
    }
    sort(g.begin(), g.end());
    g.erase(unique(g.begin(), g.end()), g.end());
    n = g.size();
    for (int i = 1; i <= n; i++) {
        mp[g[i - 1]] = i;
        fa[i] = i;
        fa[i + n] = i + n;
    }
    int i = 1;
    for (; i <= m; i++) {
        a = mp[q[i].a - 1], b = mp[q[i].b];
        if (q[i].c) {
            if (find(a) == find(b) || find(a + n) == find(b + n)) break;
            join(a, b + n); // 合并a的奇数域和b的偶数域
            join(a + n, b); // 合并a的偶数域和a的奇数域
        } else {
            if (find(a) == find(b + n) || find(a + n) == find(b)) break;
            join(a, b);     // 合并a的奇数域和b的奇数域
            join(a + n, b + n);  // 合并a的偶数域和b的偶数域
        }
    }
    cout << i - 1 << endl;
    return 0;
}

反向并查集

星球大战

求每次拆边后的连通块个数。$(m \in [1, 2e5], n \in [1, 2*m])$

Solution

拆边很难维护集合数量，考虑离线后反过来建图。这样便相当于每次增加增加一条边，查询两个点是否为同一个集合即可知道集合数量是否减少。

Code

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
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;

int n, m, k, pre[N], b[N], vis[N];

vector<int> g[N];

int find(int x) {
  int i = x, j = x;
  while (i != pre[i])
    i = pre[i];
  while (i != j) {
    int temp = pre[j];
    pre[j] = i;
    j = temp;
  } 
  return i;
}

bool join(int x, int y) {
  int fx = find(x), fy = find(y);
  if (fx != fy) {
    pre[fx] = fy;
    return true;
  }
  return false;
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    pre[i] = i;
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  cin >> k;
  for (int i = 1; i <= k; i++) {
    cin >> b[i];
    vis[b[i]] = 1;
  }
  int res = n - k;
  for (int i = 0; i < n; i++) {
    if (vis[i]) continue;
    for (int j = 0; j < g[i].size(); j++) {
      int x = g[i][j];
      if (!vis[x]) {
        if (join(i, x)) res--;
      }
    }
  }
  b[k + 1] = res;
  for (int i = k; i >= 1; i--) {
    res++;
    vis[b[i]] = 0;
    for (int j = 0; j < g[b[i]].size(); j++) {
      if (!vis[g[b[i]][j]] && join(b[i], g[b[i]][j])) 
        res--;
    }
    b[i] = res;
  }
  for (int i = 1; i <= k + 1; i++) 
    cout << b[i] << endl;
  return 0;
}

Total Eclipse

给你 $n$ 个节点 $m$ 条边的图，每个点有一个权值，你现在要做的操作是选择一个连通图，并将其中的每一个点的权值都减一，问你最少需要多少次才能将所有的点都变为0。$(1≤n≤100000, 1≤m≤200000)$

Solution

贪心地想，每次必然是选择权值最小的点，然后联通的边都减少该权值，但这样很难维护，因此可以考虑反向。

每次选择权值最大的点，然后这个点需要减少到和次小的点一样的权值，即减少的权值为和次小点权值之差。由于一次可以减少一个联通块，因此我们只需要乘以当前点联通块个数即可。

Code

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

int t, n, m, pre[N], vis[N];

vector<int> g[N];

struct Node {
  long long w;
  int id;
} q[N];

bool cmp(Node x, Node y) { return x.w > y.w; }

int find(int x) {
  int i = x, j = x;
  while (i != pre[i]) i = pre[i];
  while (j != i) {
    int temp = pre[j];
    pre[j] = i;
    j = temp;
  }
  return i;
}

bool join(int x, int y) {
  int fx = find(x), fy = find(y);
  if (fx != fy) {
    pre[fx] = fy;
    return true;
  }
  return false;
}

int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &n, &m);
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++) {
      scanf("%lld", &q[i].w);
      q[i].id = i;
      pre[i] = i;
      g[i].clear();
    }
    for (int i = 1; i <= m; i++) {
      int u, v;
      scanf("%d%d", &u, &v);
      g[u].push_back(v);
      g[v].push_back(u);
    }
    long long cnt = 0, res = 0;
    sort(q + 1, q + n + 1, cmp);
    q[n + 1].w = 0;
    for (int i = 1; i <= n; i++) {
      cnt++;
      vis[q[i].id] = 1;
      for (auto x : g[q[i].id]) {
        if (vis[x] && join(x, q[i].id)) cnt--;
      }
      res += cnt * (q[i].w - q[i + 1].w);
    }
    printf("%lld\n", res);
  }
  return 0;
}

并查集拓展

https://www.benboby.top/2020/10/%E5%B9%B6%E6%9F%A5%E9%9B%86%E6%8B%93%E5%B1%95.html

作者

Benboby

发布于

2020-10-29

更新于

2021-01-28

许可协议

#

链接

分类

最新文章

归档

标签

C++内存管理1
C++基础3
C++面向对象3
DFS1
JVM3
Java反射1
Java基础2
Java多线程1
Makefile1
MySQL1
RMQ1
STL7
Vim1
二分2
动态规划14
区间dp3
博弈论1
回文1
图论2
多校训练3
字典树1
并查集4
思维15
操作系统2
数学7
最小生成树1
树2
树形dp2
树状数组5
状压dp3
线性dp1
网络编程1
背包dp2
计数dp5
计算机网络1
记忆化搜索2
设计模式2
贪心10
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×