[模板] Disjoint Set
這幾天一直用到disjoint set，而且正好要寫考幹題的 蓋捷運 那一題，反正DSU也不難刻，所以就決定真正開始準備自己的模板庫了，以下為以前參考了OTOTOT的程式碼後才寫出來的。 class DSU { private: vector<int> fa,sz; public: void init(int n) { fa.resize(n+1), sz.resize(n+1,1); iota(fa.begin(),fa.end(),0); } int find (int x) { return (x==fa[x])?x:fa[x]= find (fa[x]); } bool same (int x,int y) { return find(x)== find (y); } void unite (int x,int y) { if( same (x,y)) return; if(sz[ find (x)] < sz[ find (y)]) swap(x,y); fa[ find (y)] = find(x); sz[ find (x)] += sz[ find (y)]; } };