Cod sursa(job #2859867)

Utilizator BereaBerendea Andrei Berea Data 2 martie 2022 08:33:15
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>

using namespace std;
const int MAXN=5e2+5;
int n,m,type,x,y;
int v[MAXN],h[MAXN],t[MAXN];

ifstream cin("disjoint.in");
ofstream cout("disjoint.out");

int findroot(int nod)
{
	if (t[nod]==nod) return nod;
	else return findroot(t[nod]);
}

int Union(int rot1,int rot2)
{
	if (h[rot1]>h[rot2]) t[rot2]=rot2;
	else if (h[rot1]<h[rot2]) t[rot1]=rot2;
	else if (h[rot1]==h[rot2])
	{
		t[rot1]=rot2;
		h[rot2]++;
	}
}

int main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		t[i]=i;
		h[i]=1;
	}
	for (int i=1;i<=m;i++)
	{
		cin>>type>>x>>y;
		if (type==1) if (findroot(x)!=findroot(y)) Union(findroot(x),findroot(y));
		if (type==2)
		{
			if (findroot(x)==findroot(y)) cout<<"DA\n";
			else cout<<"NU\n";
		}
	}
}