Cod sursa(job #1757769)

Utilizator dodecagondode cagon dodecagon Data 15 septembrie 2016 19:57:43
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 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[find(p[i])]++;
    m=0;
    for (i=1;i<=n;++i)
        if (fr[i]!=0) 
            m++;
    fprintf(fopen("dfs.out","w"),"%d",m);
 
    return 0;
}