面试题--最小并查集

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

最小并查集

题目:

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

输入:

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

输出:

1
至少还要输出1条

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

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

#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();
    }
}