下面给出了一个简洁的并查集实现
/************************************************************************* > File Name: union_find.cpp > Author: Yuji CAO > Mail: yujicao@amazon.com > Created Time: 2016年08月14日 星期日 10时41分07秒 ************************************************************************/ #include<iostream> #include<vector> #include<unordered_map> #include<unordered_set> #include<sstream> #include<list> #include<queue> #include<stack> #include<string> #include<utility> #include<algorithm> using namespace std; class UnionFind { public: UnionFind(int n) { s.resize(n); for (int i = 0; i < n; ++i) { s[i] = i; } } void uni(int t1, int t2) { int r1 = find(t1); int r2 = find(t2); if (r1 != r2) { s[r2] = r1; } } int find(int t) { if (s[t] == t) return t; s[t] = find(s[t]); return s[t]; } void print() { for (int i = 0; i < s.size(); ++i) { cout<<i<<"\t"; } cout<<endl; for (int i = 0; i < s.size(); ++i) { cout<<s[i]<<"\t"; } cout<<endl; } private: vector<int> s; }; int main() { UnionFind uf(10); uf.uni(1,2);//1<-2 uf.uni(2,3);//1<-2;1<-3 cout<<uf.find(2)<<endl; cout<<uf.find(3)<<endl; uf.uni(8,9);//1<-2 uf.print(); return 0; }