上个星期参加了网易的面试题,非常难,考完后拿回来和大佬同学讨论了一下才明白要怎么做,这里记录思考过程。
最小并查集
题目:
有一个村庄,村庄中部分用户已经通了下水管道,但是还有一些用户没有通,请问至少要多建多少根下水管道才能让所有的用户都联通呢?
输入:
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 76 77
| #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; 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); 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(); } }
|