Cod sursa(job #202980)

Utilizator shade4529Popescu Mihai shade4529 Data 12 august 2008 15:27:15
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<stdio.h>
FILE *f,*g;
long c[100005],t[3][400005],viz[100005],n,m,i,j,nr,x,y,v;
int dfs(long k)
{ long v=c[k]; viz[k]=1;
  while(t[2][v]!=0)
   { if(!viz[t[1][v]]) dfs(t[1][v]);
     v=t[2][v];
   }
  if(!viz[t[1][v]]) dfs(t[1][v]);
  return 0;
}
int main()
{ f=fopen("dfs.in","r"); g=fopen("dfs.out","w");
  fscanf(f,"%ld%ld",&n,&m);
  nr=1;
  for(i=1;i<=m;i++)
   { fscanf(f,"%ld%ld",&x,&y);
     if(!c[x])
      { while(t[1][nr]!=0) nr++;
	c[x]=nr; t[1][nr]=y;
      }
     else
      { v=c[x];
	while(t[2][v]!=0) v=t[2][v];
	while(t[1][nr]!=0) nr++;
	t[2][v]=nr; t[1][nr]=y;
      }
   }
  nr=0;
  for(i=1;i<=n;i++)
   if(!viz[i])
    { nr++;
      dfs(i);
    }
  fprintf(g,"%ld",nr);
  fclose(g);
  return 0;
}