Union/find

[Hsue66]

include

include

using namespace std;

define MAX 1000

int N; int parent[MAX], level[MAX];

void init() { for (int i = 0; i < N; i++) { parent[i] = i; level[i] = 1; } }

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

void uni0n(int u, int v) { u = find(u); v = find(v);

if (u == v) {
    cout << "already connected" << endl;
    return;
}
if (level[u] > level[v])
    swap(u, v);
parent[u] = v;
if (level[u] == level[v])
    level[v]++;

}

void show() { for (int i = 0; i < N; i++) cout << parent[i] << " "; cout << endl; }

int main() { N = 5; init();

show();
uni0n(0, 1);
uni0n(0, 2);
show();

uni0n(3, 4);
show();

uni0n(0, 4);
show();

uni0n(1, 4);
show();

}