Cod sursa(job #875766)

Utilizator howsiweiHow Si Wei howsiwei Data 10 februarie 2013 19:24:48
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
using namespace std;

class DisjSet {
public:
	DisjSet(int nelem): parent(nelem+1) {}
	int find(int x);
	void unionSet(int root1, int root2); 
private:
	vector<int> parent; // if root contain negative of parent
};

int DisjSet::find(int x) {
	if (parent[x]<=0) return x;
	else return parent[x]=find(parent[x]);
}

void DisjSet::unionSet(int root1, int root2) {
	if (root1==root2) return;
	if (parent[root1]>parent[root2]) {
		parent[root1]=root2;
	}
	else {
		parent[root2]=root1;
		if (parent[root1]==parent[root2])
			--parent[root1];
	}
}

int main() {
	ifstream fin("disjoint.in");
	ofstream fout("disjoint.out");
	int nelem, noper;
	fin >> nelem >> noper;
	int type_oper, elem1, elem2;
	DisjSet all(nelem);
	for (int i=0; i<noper; i++) {
		fin >> type_oper >> elem1 >> elem2;
		if (type_oper==1) all.unionSet(elem1,elem2);
		else {
			if (all.find(elem1)==all.find(elem2)) fout << "YES\n";
			else fout << "NO\n";
		}
	}
	return 0;
}