Cod sursa(job #1757763)

Utilizator dodecagondode cagon dodecagon Data 15 septembrie 2016 19:42:00
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <stdio.h>

int rg[100009],fr[100009],n,m,i,x,y,r,p[100009];

int find(int x)
{
   r=x;
   while (r!=p[r])
   	 r=p[r];
   	while (x!=p[x])
   	{
   		x=p[x];
   		p[x]=r;
   	}
   	return r;
}

void uneste(int x,int y)
{
   x=find(x);
   y=find(y);
    if (x!=y)
    {
       if (rg[x]>rg[y])
       {
       	 p[y]=x;
       	 rg[x]+=rg[y];
       } else 
       {
       	p[x]=y;
       	rg[y]+=rg[x];
       }
    }
}

int main(int argc, char const *argv[])
{
	
	FILE * in =fopen("dfs.in","r");
	fscanf(in,"%d%d",&n,&m);

	for (i=1;i<=n;++i)
		p[i]=i,rg[i]=1;

	  while (m--)
	  {
        fscanf(in,"%d%d",&x,&y);
        uneste(x,y);
	  }

	 
   
   for (i=1;i<=n;++i)
   	 fr[p[i]]++;
   	m=0;
   	for (i=1;i<=n;++i)
   		if (fr[i]!=0) 
   			m++;
    fprintf(fopen("dfs.out","w"),"%d",m);

	return 0;
}