# 目次

• 目次
  • Class
  • Usage

# Class

要素の重複のない複数の集合を管理するDisjoint Setというデータ構造.

• コンストラクタに要素の数を渡して初期化する.初期状態ではすべての要素がそれぞれの集合をなす。
• sameで２つの要素が同じ集合に属するかどうかを判定する.
• uniteで２つの要素が含まれる集合を統合する.

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

class DisjointSet {
public:
    DisjointSet(int n) {
        rank.resize(n);
        parent.resize(n);
        for (int i=0; i<n; i++) rank[i] = 0, parent[i] = i;
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    void unite(int x, int y) {
        x = root(x), y = root(y);
        if (rank[x] > rank[y]) {
            parent[y] = x;
        } else {
            parent[x] = y;
            if (rank[x] == rank[y]) rank[y]++;
        }
    }
    
private:
    vector<int> rank;
    vector<int> parent;
    
    int root(int x) {
        if (x != parent[x]) {
            parent[x] = root(parent[x]);
        }
        
        return parent[x];
    }
};

# Usage

無効グラフに閉路が含まれるかを判定する.

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

struct Edge { int src, dst; };

bool hasCycle(vector<Edge> &edges, int n) {
    DisjointSet ds(n);
    
    for (auto edge: edges) {
        if (ds.same(edge.src, edge.dst)) {
            return true;
        }
        
        ds.unite(edge.src, edge.dst);
    }
    
    return false;
}


int main(void) {
    vector<Edge> edges;
    edges.push_back({ 0, 1 });
    edges.push_back({ 1, 2 });
    edges.push_back({ 2, 0 });
    if (hasCycle(edges, 3)) cout << "yes";
    else cout << "no";
    cout << endl;
}