Cod sursa(job #2810867)

Utilizator teofilotopeniTeofil teofilotopeni Data 30 noiembrie 2021 14:34:53
Problema Paduri de multimi disjuncte Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

vector<int> nodes[100001];
bitset<100001> finded;

void parcurge(int i, int search) {
	if (i == search || finded[i] == 1) {
		finded[i] = 1;
		return;
	}
	finded[i] = 1;
	for (int j = 0; j < nodes[i].size(); j++) {
		parcurge(nodes[i][j], search);
	}
}

int main() {
	freopen("disjoint.in", "r", stdin);
	freopen("disjoint.out", "w", stdout);
	int nr, operations;
	string answer[] = { "NU\n", "DA\n" };
	cin >> nr >> operations;
	while (operations--) {
		int cod, x, y;
		cin >> cod >> x >> y;
		if (cod == 1) {
			nodes[x].push_back(y);
			nodes[y].push_back(x);
		}
		else {
			for (int i = 0; i < 100001; i++) {
				finded[i] = 0;
			}
			parcurge(x, y);
			cout << answer[finded[y]];
		}
	}
	return 0;
}