Union-find (disjoint set)

 

새로운 걸 배웠다

 

 

 

코드가 간단해서 너무 좋다

 

vector<int> parent;

void    init(int n)
{
    parent.resize(n + 1);

    for (int i = 0; i <= n; i++)
        parent[i] = i;
}

int     find(int x)
{
    if (x == parent[x])
        return x;
    return (parent[x] = find(parent[x]));
}

void    merge(int x, int y)
{
    x = find(x);
    y = find(y);
    
    parent[x] = y;
}