Cod sursa(job #2115946)
Utilizator | Data | 27 ianuarie 2018 11:29:57 | |
---|---|---|---|
Problema | Paduri de multimi disjuncte | Scor | 40 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.64 kb |
#include<iostream>
#include<fstream>
using namespace std;
ofstream g("disjoint.out");
int v[100001];
int boss(int a)
{
if(v[a]==a)
return v[a];
return v[a]=boss(v[a]);
}
void joint(int x,int y)
{
v[boss(y)]=boss(x);
}
void query(int x, int y)
{
if(boss(x)==boss(y))
g<<"DA"<<endl;
else
g<<"NU"<<endl;
}
int main ()
{
ifstream f("disjoint.in");
int N,M,i,x,y,q;
f>>N>>M;
for(i=1;i<=N;i++)
v[i]=i;
for(i=1;i<=M;i++)
{
f>>q>>x>>y;
if(q==1)
joint(x,y);
else
query(x,y);
}
return 0;
}