Cod sursa(job #3373384)

Utilizator AlexRocaRoca Alexandru AlexRoca Data 6 noiembrie 2026 19:44:42
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("disjoint.in");
ofstream cout("disjoint.out");
struct pd
{
	vector<int> p;
	pd(int n) {p.resize(n, -1);}
	int rad(int x)
	{
		if (p[x]==-1) return x;
        else
        {
			p[x]=rad(p[x]);
			return p[x];
		}
	}
	bool query(int a, int b) {return rad(a)==rad(b);}
	void join(int a, int b)
	{
		a=rad(a);
		b=rad(b);
		if(a!=b) p[a]=b;
	}
};

int main()
{
	int n, m, op, a, b;
	cin>>n>>m;
	pd dsu(n);
	for(int i=0; i<m; i++)
    {
		cin >> op >> a >> b;
		a--;
		b--;
		if(op==1) dsu.join(a, b); else if(dsu.query(a, b)) cout<<"DA\n"; else cout<<"NU\n";
    }
}