面试题--最小并查集

上个星期参加了网易的面试题,非常难,考完后拿回来和大佬同学讨论了一下才明白要怎么做,这里记录思考过程。

最小并查集

题目:

有一个村庄,村庄中部分用户已经通了下水管道,但是还有一些用户没有通,请问至少要多建多少根下水管道才能让所有的用户都联通呢?

输入:

5 3 (5个用户,已经修筑了3条线)
1 2 (修筑了下水道的用户)
2 3
3 4

输出:

1
至少还要输出1条

仔细看会发现是一个最小并查集的题目,难点就在于如何将已经连通的城市表示出来。这里采用的模型,也就是说,我们通过遍历边,让 边两侧的点都挂在同一棵树下,从而形成一个个集合。
树我们就用数组来表示,然后数组中的元素表示父节点。每当我们需要判断当前集合的值的时候,我们就从子节点往上查找,直到找到根节点的值。查找的过程写成递归的形式就好。
最后我们让每个子节点都直接链接到根节点上,最后对数组排序,就能很容易的找到有哪几个集合了。

(感谢dalao学渣晖sir提供的思路和讨论)

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
74
75
#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;
struct line
{
int begin, end;
};
int Find(int x, int* nodes)
{
return x == nodes[x]?x:nodes[x] = Find(nodes[x], nodes);//递归找到根节点
}
int cmp(int a, int b)
{
return a > b;
}
int nodes[1000];
int main()
{
vector<line> Lines;
int v, n;
int b, e;
while(cin >> v >> n){
for(int i = 0; i <= v; i++){
nodes[i] = i;
}
memset(nodes, 0, n*sizeof(int));
//首先生成点的集合和边的集合
if(n == 0){
cout << v - 1 << endl;
break;
}
for(int i = 0; i < n; i++){
struct line L = {};
cin >> b >> e;
//nodes[b] = b;
//nodes[e] = e;
L.begin = b;
L.end = e;
Lines.push_back(L);
}
//之后对应索引处的点为该点的前驱节点
for(int j = 0; j < Lines.size(); j++){
int x = Find(Lines[j].begin, nodes);
int y = Find(Lines[j].end, nodes);
//将nodes[i]保存的元素替换成前驱节点
if(x != y){
nodes[x] = nodes[y];
}
}
// 将每个节点直接连在根节点上
for (int i = 1; i <= v; i++) {
nodes[i] = Find(nodes[i], nodes);
}
sort(&nodes[1] ,&nodes[v + 1] , cmp);
int cur;
int cnt = 0;
cur = nodes[1];
for(int i = 1; i <= v; i++){
if(nodes[i]!= cur){
cur = nodes[i];
cnt++;
}
}
cout << cnt << endl;
Lines.clear();
}
}