Cod sursa(job #1316546)
Utilizator | Dinu Radu RaduGabriel2012 | Data | 13 ianuarie 2015 21:44:36 |
---|---|---|---|
Problema | Paduri de multimi disjuncte | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.51 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("disjoint.in");
ofstream g("disjoint.out");
int n,m,t,dad[100005];
int Set(int x)
{
if (dad[x]) dad[x]=Set(dad[x]);
if (dad[x]) return dad[x];
else return x;
}
int main()
{ int i,s1,s2;
f>>n>>m;
for(i=1;i<=m;i++)
{ f>>t>>s1>>s2;
if (t==1) dad[Set(s2)]=Set(s1);
else
{
if (Set(s2)==Set(s1)) g<<"DA\n";
else g<<"NU\n";
}
}
return 0;
}