Cod sursa(job #389633)

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

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

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