Cod sursa(job #2892921)

Utilizator DooMeDCristian Alexutan DooMeD Data 23 aprilie 2022 23:25:37
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5;

int comp[nmax+5], dim[nmax+5];

int Find(int node) {
	if(comp[node] == node) return node;
	comp[node] = Find(comp[node]);
	return comp[node];
}

void Union(int a, int b) {
	int ra = Find(a), rb = Find(b);
	if(ra == rb) return;
	if(dim[ra] > dim[rb]) swap(ra, rb);
	dim[rb] += dim[ra];
	comp[ra] = comp[rb];
}

int main () {
    ifstream f("disjoint.in");
    ofstream g("disjoint.out");
    
    int n, m; cin >> n >> m;
    for(int i=1; i<=n; i++) comp[i] = i, dim[i] = 1;
    for(int i=1; i<=m; i++) {
		int type, a, b; cin >> type >> a >> b;
		if(type==1) Union(a, b);
		else cout << (Find(a) == Find(b) ? "DA\n" : "NU\n");
	}
    return 0;
}