Cod sursa(job #202186)

Utilizator adrianraduleaRadulea Adrian adrianradulea Data 6 august 2008 18:04:23
Problema Parcurgere DFS - componente conexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<stdio.h>
FILE *f,*g;
long n,m,nr,i,x,y,a[100001],j,viz[100001];
int main()
{ f=fopen("dfs.in","r"); g=fopen("dfs.out","w");
  fscanf(f,"%ld%ld",&n,&m);
  nr=0;
  for(i=1;i<=m;i++)
   { fscanf(f,"%ld%ld",&x,&y);
     if(i==1) { a[x]=1; a[y]=1; nr=1; }
     else
      { if(a[x]&&!a[y]) a[y]=a[x];
	else if(a[y]&&!a[x]) a[x]=a[y];
	else if(!a[x]&&!a[y]) { nr++; a[x]=a[y]=nr; }
	else if(a[x]&&a[y]) for(j=1;j<=n;j++) if(a[j]==a[x]) a[j]=a[y];
      }
   }
  nr=0;
  for(i=1;i<=n;i++) if(a[i]==0) nr++;
  else if(!viz[a[i]])
   { viz[a[i]]=1;
     nr++;
   }
  fprintf(g,"%ld",nr);
  fclose(g);
  return 0;
}