Cod sursa(job #389621)

Utilizator nautilusCohal Alexandru nautilus Data 1 februarie 2010 22:19:44
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include<fstream.h>
#define max 100001

int n,m,x,y,nr,st,dr,a[max][max],v[max];

void dfs(int k)
{
 int i;
 
 for (i=1; i<=a[k][0]; i++)
	 {
	  v[a[k][i]]=v[k];
	  nr--;
	  dfs(a[k][i]);
	 }
	
}

int main()
{
 int i,j;
	
 ifstream fin("dfs.in");
 fin>>n>>m;
 for (i=1; i<=m; i++)
	 {
	  fin>>x>>y;
	  a[x][0]++; a[x][a[x][0]]=y;
	 }
 
 for (i=1; i<=n; i++)
	 v[i]=i;
 
 nr=n;
 for (i=1; i<=n; i++)
	 if (v[i]==i)
	     dfs(i);
 
	
 ofstream fout("dfs.out");
 fout<<nr;
 
 fin.close();
 fout.close();
 
 return 0;
}