Cod sursa(job #656268)

Utilizator danirotRotaru Daniel danirot Data 4 ianuarie 2012 13:28:43
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<stdio.h>
#define N 100001
int v[N],n,m,i,s,x,y,s1,s2;
int reu(int a)
{
 int b=a,c;
 while(b!=v[b])
  b=v[b];
  while(a!=v[a])
  {
		c=v[a];
		v[a]=b;
		a=b;
	}
	return a;
}
int main()
{
    freopen("disjoint.in", "r", stdin);
    freopen("disjoint.out", "w", stdout);
    scanf("%d%d",&n,&m);
	 for(i=1;i<=n;i++)
	  v[i]=i;
	  for(i=1;i<=m;i++)
	  {

			scanf("%d%d%d",&s,&x,&y);
			if(s==1)
			{
			s1=reu(x);
			s2=reu(y);
			v[s2]=s1;}
			if(s==2)
			{
				s1=reu(x);
				s2=reu(y);
				if(s1==s2)
				 printf("DA\n");
				else printf("NU\n");
			}
		}
		return 0;
	}