顺丰科技算法笔试题解：学术交流（并查集）

#include <unordered_map>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class UnionFindSet {
public:
    int getMachineNum(vector<vector<int>> matrix, int person_num, int language_num, int num) {   //num 为人数
        if (!matrix.size())
            return ;

        vector<vector<int>> tmp(language_num);
        for (int i = ; i < num; i++) {
            tmp[matrix[i][] - ].push_back(matrix[i][] - );   // 每种语言都有哪些人使用, 索引从零开始
        }

        // 输出
        for (int i = ; i < tmp.size(); i++) {
            cout << "语言类别 " << i +  << " 会的人为：";
            for (int j = ; j < tmp[i].size(); j++) {
                cout << tmp[i][j] +  << " ";
            }
            cout << endl;
        }

        for (int i = ; i < person_num; i++) {
            father_map[i] = i;
            size_map[i] = ;    // 初始化并查集
        }
        count = person_num;     // count初始化

        // 按照会的语言对人的标号进行划分set，如果一个人会A,B语言，则A和B集的所有人都会在一个集合
        for (int i = ; i < tmp.size(); i++) {
            if (tmp[i].size() >= ) {
                for (int j = ; j < tmp[i].size() - ; j++) {
                    Union(tmp[i][j], tmp[i][j + ]);
                }
            }
        }
        return count - ;
    }

    int findRep(int i) {
        int tmp = father_map[i];
        if (tmp != i) {
            tmp = findRep(tmp);
        }
        father_map[i] = tmp;
        return tmp;    // 每次查找，就将其上级节点都挂在代表节点上
    }

    void Union(int i, int j) {
        int p = findRep(i);
        int q = findRep(j);
        if (p == q)
            return;
        if (size_map[p] < size_map[q]) {
            father_map[p] = q;
            size_map[q] += size_map[q];
        }
        else {
            father_map[q] = p;
            size_map[p] += size_map[p];
        }
        count--;
    }

private:
    unordered_map<int, int> father_map;
    unordered_map<int, int> size_map;
    int count;
};

int main() {
    int m, n, k;
    cin >> m >> n >> k;
    vector<vector<int>> matrix(k, vector<int>());
    for (int i = ; i < k; i++) {
        for (int j = ; j < ; j++) {
            cin >> matrix[i][j];
        }
    }

    UnionFindSet set;
    int count = set.getMachineNum(matrix, m, n, k);
    cout << "res: " << count << endl;
    system("PAUSE");
    return ;
}