算法常用模板：并查集

C++实现：

#include <iostream>
#include <vector>
#include <map>

using namespace std;

class UnionFindSet {

public:
    //(key,value)表示，key的父节点，是value，（Data_A，Data_B）代表，Data_A的父节点是Data_B
    map<int, int> fatherMap;
    map<int, int> sizeMap;

    UnionFindSet(vector<int> nodes) {
        makeSets(nodes);
    }

    void makeSets(vector<int> nodes) {
        fatherMap.clear();
        sizeMap.clear();
        for (int i=0;i< nodes.size();i++) {
            fatherMap[nodes[i]]=nodes[i];
            sizeMap[nodes[i]]=1;
        }
    }

    int findHead(int node) {
        int father = fatherMap[node];
        if (father != node)
            father = findHead(father);
        fatherMap[node]= father;
        return father;
    }

    bool isSameSet(int a, int b) {
        return findHead(a) == findHead(b);
    }

    void Union(int a, int b) {
        int aHead = findHead(a);
        int bHead = findHead(b);
        if (aHead != bHead) {
            int aSetSize = sizeMap[aHead];
            int bSetSize = sizeMap[bHead];
            if (aSetSize <= bSetSize) {
                fatherMap[aHead]=bHead;
                sizeMap[bHead]=aSetSize + bSetSize;
            } else {
                fatherMap[bHead]= aHead;
                sizeMap[aHead]= aSetSize + bSetSize;
            }
        }
    }
};

int main(){
	int n=10;
	vector<int> ini;
	for(int i=0;i<n;i++)
		ini.push_back(i);
	
	UnionFindSet fs(ini);
	
	fs.Union(1,2);
	cout<<fs.isSameSet(1,2)<<endl;
		
	return 0;
}

---

Java实现：

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class UnionSet {
    public static void main(String[] args) {
        Data[] datas = new Data[5];
        List<Data> list = new LinkedList<Data>();
        for (int i = 0; i < 5; i++) {
            datas[i] = new Data();
            list.add(datas[i]);
        }
        UnionFindSet unionFindSet = new UnionFindSet(list);
        unionFindSet.union(datas[1],datas[2]);
        System.out.println(unionFindSet.isSameSet(datas[1],datas[2]));
    }

    public static class Data {

    }

    public static class UnionFindSet {
        //(key,value)表示，key的父节点，是value，（Data_A，Data_B）代表，Data_A的父节点是Data_B
        public HashMap<Data, Data> fatherMap;
        public HashMap<Data, Integer> sizeMap;

        public UnionFindSet(List<Data> nodes) {
            fatherMap = new HashMap<Data, Data>();
            sizeMap = new HashMap<Data, Integer>();
            makeSets(nodes);
        }

        private void makeSets(List<Data> nodes) {
            fatherMap.clear();
            sizeMap.clear();
            for (Data node : nodes) {
                fatherMap.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        private Data findHead(Data node) {
            Data father = fatherMap.get(node);
            if (father != node)
                father = findHead(father);
            fatherMap.put(node, father);
            return father;
        }

        public boolean isSameSet(Data a, Data b) {
            return findHead(a) == findHead(b);
        }

        public void union(Data a, Data b) {
            if (a == null || b == null)
                return;
            Data aHead = findHead(a);
            Data bHead = findHead(b);
            if (aHead != bHead) {
                int aSetSize = sizeMap.get(aHead);
                int bSetSize = sizeMap.get(bHead);
                if (aSetSize <= bSetSize) {
                    fatherMap.put(aHead, bHead);
                    sizeMap.put(bHead, aSetSize + bSetSize);
                } else {
                    fatherMap.put(bHead, aHead);
                    sizeMap.put(aHead, aSetSize + bSetSize);
                }
            }
        }
    }
}