Cod sursa(job #2425542)

Utilizator qusyNastase Alexandru qusy Data 24 mai 2019 21:22:14
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
int tata[100009], grad[100009];

int find_father(int x)
{
	if (x == tata[x])
		return x;
	return find_father(tata[x]);
}


int main()
{
	int n, m, tip_operatie, x, y;
	fin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		tata[i] = i;
		grad[i] = 1;
	}
	for (int i = 0; i < m; i++)
	{
		fin >> tip_operatie;
		fin >> x >> y;
		if (tip_operatie == 1)
		{
			int fx = find_father(x);
			int fy = find_father(y);
			if (grad[fx] < grad[fy])
			{
				tata[fx] = fy;
				grad[fy] += grad[fx];
			}
			else
			{
				tata[fy] = fx;
				grad[fx] += grad[fy];
			}
		}
		if (tip_operatie == 2)
		{
			int father_x = find_father(x);
			int father_y = find_father(y);
			if (father_x == father_y)
				fout << "DA\n";
			else
				fout << "NU\n";
		}
	}
	return 0;
}