Cod sursa(job #295157)

Utilizator adrianraduleaRadulea Adrian adrianradulea Data 3 aprilie 2009 00:24:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<stdio.h>
int viz[100000];
long t[4][400000],c[100000],m,liber,i,x,y,p,n,nr;
FILE *f,*g;
void df(long k)
{ long p; viz[k]=1;
  p=c[k];
  while(p!=0)
   { if(!viz[t[1][p]]) df(t[1][p]);
     p=t[2][p];
   }
}
int main()
{ f=fopen("dfs.in","r"); g=fopen("dfs.out","w");
  fscanf(f,"%ld%ld",&n,&m);
  liber=1;
  for(i=1;i<=m;i++)
   { fscanf(f,"%ld%ld",&x,&y);
     if(c[x]==0) { c[x]=liber; t[1][liber]=y; liber++; }
     else
      { p=c[x];
	while(t[2][p]!=0) p=t[2][p]; t[2][p]=liber; t[1][liber]=y; liber++;
      }
     if(c[y]==0) { c[y]=liber; t[1][liber]=x; liber++; }
     else
      { p=c[y];
	while(t[2][p]!=0) p=t[2][p]; t[2][p]=liber; t[1][liber]=x; liber++;
      }
   }
  nr=0;
  for(i=1;i<=n;i++) if(!viz[i])
   { nr++; df(i); }
  fprintf(g,"%ld",nr);
  fclose(g);
  return 0;
}