Cod sursa(job #2582917)

Utilizator DawlauAndrei Blahovici Dawlau Data 17 martie 2020 15:06:29
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <vector>

using namespace std;

class Union_Find{

	private:

		vector <int> dad;
		vector <int> level;

	public:

		Union_Find(const int &V) {

			dad.resize(1 + V);
			level.resize(1 + V);

			for (int node = 1; node <= V; ++node) {

				dad[node] = node;
				level[node] = 1;
			}
		}

		void Union(int node1, int node2) {

			if (level[node1] > level[node2])
				dad[node2] = node1;
			else dad[node1] = node2;

			if (level[node1] == level[node2])
				++level[node2];
		}

		int Find(int node) {

			int root = node;
			for (; root != dad[root]; root = dad[root]);

			while (node != root) {

				int auxNode = node;
				node = dad[node];
				dad[auxNode] = root;
			}

			return root;
		}
};

ifstream fin("disjoint.in");
ofstream fout("disjoint.out");

int main() {

	int N, M;
	fin >> N >> M;

	Union_Find dsu(N);
	for (; M; --M) {

		int op, x, y;
		fin >> op >> x >> y;

		int root1 = dsu.Find(x);
		int root2 = dsu.Find(y);

		if (op == 1) dsu.Union(root1, root2);
		else {

			if (root1 == root2)
				fout << "DA\n";
			else fout << "NU\n";
		}
	}
}