Mai intai trebuie sa te autentifici.
Cod sursa(job #432571)
Utilizator | Data | 2 aprilie 2010 15:39:29 | |
---|---|---|---|
Problema | Paduri de multimi disjuncte | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.9 kb |
#include <algorithm>
using namespace std;
#define DIM 100005
int r[DIM],t[DIM];
int n,m;
int find (int x)
{
if (x!=t[x])
t[x]=find (t[x]);
return t[x];
}
inline void unite (int x,int y)
{
if (r[x]>r[y])
{
t[y]=x;
r[x]+=r[y];
}
else
{
t[x]=y;
r[y]+=r[x];
}
}
void solve ()
{
int i,tip,x,y;
for (i=1; i<=n; ++i)
{
t[i]=i;
r[i]=1;
}
for (i=1; i<=m; ++i)
{
scanf ("%d%d%d",&tip,&x,&y);
if (tip==1)
unite (find (x),find (y));
else
if (find (x)==find (y))
printf ("DA\n");
else
printf ("NU\n");
}
}
int main ()
{
freopen ("disjoint.in","r",stdin);
freopen ("disjoint.out","w",stdout);
scanf ("%d%d",&n,&m);
solve ();
return 0;
}