数据结构专题训练赛03解题报告

并查集

目标

  • 将两个集合合并
  • 查询两个元素是否在同一集合内

构造

每个集合用一棵树表示,用根节点的编号表示整个集合的编号,开一个数组 \(p[x]\) ,表示编号为 \(x\) 的元素的父节点编号

  • \(p[x] = = x, x\) 为树根。
  • \(x\) 的集合编号:while(p[x] != x) x = p[x]
  • 合并两个元素所在集合,设 \(px,py\) 表示 \(x,y\) 的集合编号,p[px]=py

路径压缩

这样的确可以达成目的,但是显然效率实在太低。为什么呢?因为我们使用了太多没用的信息,我的祖先是谁与我父亲是谁没什么关系,这样一层一层找太浪费时间,不如我直接当祖先的儿子,问一次就可以出结果了。甚至祖先是谁都无所谓,只要这个人可以代表我们家族就能得到想要的效果。 把在路径上的每个节点都直接连接到根上 ,这就是路径压缩。——OI-Wiki

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int n, p[N];
void init()//初始化
{
for(int i = 1; i <= n; i++) p[i]=i;
}
int find(int x)//查询x的集合编号
{
if(p[x]!=x) p[x] = find(p[x]);
return p[x];
}
void merge(int x, int y)//合并xy所在集合
{
x = find(x), y = find(y);
if(x == y) return;
p[x] = y;
}

扩展

维护size的并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义,表示祖宗节点所在集合中的点的数量

// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1;
}

// 合并a和b所在的两个集合:
size[find(b)] += size[find(a)];
p[find(a)] = find(b);

维护到祖宗节点距离的并查集

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
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}

// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}

// 合并a和b所在的两个集合:
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题,初始化find(a)的偏移量

CF731C-Socks

描述

有n只袜子,k种颜色,给定每只袜子的颜色,在m天中,问最少修改几只袜子的颜色,可以使每天要穿的袜子颜色相同。

题解

用并查集维护需要保证是同一个颜色的集合,由题意,同一天的两个编号必定在同一个集合内。

而后统计每个集合内哪一个颜色的数量最多,集合的大小减去最大的数量即为这个集合需要修改的数量。

将所有集合的贡献累加即为答案

代码

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 = 200010;
int p[N], c[N], cnt[N], n, m, k;
vector<int> v[N];
int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}

int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
{
p[i] = i;
scanf("%d", &c[i]);
}
for (int i = 1, l, r; i <= m; i++)
{
scanf("%d%d", &l, &r);
int pl = find(l), pr = find(r);
if (pl != pr)
p[pl] = pr;
}

for (int i = 1; i <= n; i++)
{
int tmp = find(i);
v[tmp].push_back(c[i]);
}
int res = 0;
for (int i = 1; i <= n; i++)
{
int tn = v[i].size(), mx = 0;
if (!tn)
continue;
for (int j = 0; j < tn; j++)
{
cnt[v[i][j]]++;
mx = max(mx, cnt[v[i][j]]);
}
for (int j = 0; j < tn; j++)
cnt[v[i][j]]--;
res += tn - mx;
}
printf("%d\n", res);
return 0;
}

CF362D Fools and Foolproof Roads

描述

给定 n 个点 m 条边的无向图,问是否能在图里添加 p 条边使得加边后存在恰好 q 个连通分量,同时请求出边权总和最小的方案。

新增边的边权为 \(min(10^{9}, S+1)\) ,其中 S 为这条边连接的两个联通块的边权之和。

题解

维护一个并查集来表示联通块,由题意要额外维护联通块的大小去计算连边的代价。

判断无解的情况:

  1. 将联通块进行了 p 次连边后依然联通块的数量大于 q
  2. 未连边前联通块数量小于 q
  3. 点的数量为 q ,且不存在边,此时若 p 非0,由于不允许自环,故无解

求最优的方案时,将联通块压入优先队列,每次取最小的两个联通块合并,保证每次合并的边权最小

若还没有用完 p 次连边就已经满足条件,则在任意一联通块内找任意两点,将剩下所有连边加在这两个点上

代码

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
71
72
73
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 10, inf = 1e9;
typedef pair<ll, ll> pii;
ll p[N], w[N], n, m, pp, q, cnt;
struct cmp
{
bool operator()(const pii p1, const pii p2)
{
return p1.first > p2.first;
}
};
priority_queue<pii, vector<pii>, cmp> blk;
ll find(ll x)
{
if (x != p[x])
p[x] = find(p[x]);
return p[x];
}
void merge(ll x, ll y, ll l)
{
ll px = find(x), py = find(y);
if (px == py)
w[px] += l;
else
{
p[px] = py;
w[py] += l + w[px];
cnt--;
}
}
int main()
{
scanf("%lld%lld%lld%lld", &n, &m, &pp, &q);
cnt = n;
for(ll i = 1; i <= n; i++) p[i] = i;
for (ll i = 1, x, y, l; i <= m; i++)
{
scanf("%lld%lld%lld", &x, &y, &l);
merge(x, y, l);
}
if(cnt - pp > q || cnt < q)
{
puts("NO");
return 0;
}
if(!m && !(q - n) && pp)
{
puts("NO");
return 0;
}
puts("YES");
for (ll i = 1; i <= n; i++)
if (i == find(i))
blk.push({w[p[i]], i});
while (cnt > q)
{
pii b1 = blk.top();
blk.pop();
pii b2 = blk.top();
blk.pop();
pp--, cnt--;
printf("%lld %lld\n", b1.second, b2.second);
p[b2.second] = b1.second;
w[b1.second] += min(inf, b1.first + b2.first + 1) + b2.first;
blk.push({w[b1.second], b1.second});
}
ll ran;
for(ran = 1; ran <= n; ran++) if(find(ran) != ran) break;
while(pp--) printf("%lld %lld\n", ran, p[ran]);
return 0;
}
----- 本文结束 感谢阅读 -----
0%