Cod sursa(job #392606)

Utilizator nautilusCohal Alexandru nautilus Data 7 februarie 2010 20:54:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<fstream>
#include<list>
#define dmax 100003

using namespace std;

long n,m,v[dmax],nrcomponente;
struct lista
	{
	 long nr;
	 list<long> L;
	} a[dmax];
	
	
void dfs(int k)
{
 list<long>::iterator i;
 
 v[k]=1;
 for (i=a[k].L.begin(); i!=a[k].L.end(); i++)
	 if (v[*i]==0)
		 dfs(*i);
}
	

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