Pagini recente » Cod sursa (job #2897946) | Cod sursa (job #1392942) | Cod sursa (job #2420147) | Monitorul de evaluare | Cod sursa (job #875766)
Cod sursa(job #875766)
#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;
}