Cod sursa(job #592194)

Utilizator thesilverhand13FII Florea Toma Eduard thesilverhand13 Data 26 mai 2011 22:30:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
 # include <fstream>
 # include <algorithm>
 # include <vector>
 # define dim 100002
 # define pb push_back
 
 using namespace std;
 
 ifstream f ("dfs.in");
 ofstream g ("dfs.out");
 
 vector <int> a[dim];
 int viz[dim];
 int n, m, sol;
 
 void dfs(int x)
 {
	 int lg, i;
	 viz[ x ] = 1;
	 lg = a[x].size();
	 for ( i = 0 ; i < lg ; i ++)
		 if ( viz[ a[ x ][ i ] ] == 0)
		 {
			 dfs( a[ x ][ i ] );
		 }
	 
 }
 
 void rezolvare()
 {
	 int i;
	 for ( i = 1 ; i <= n ; i ++ )
		 if ( viz[i] == 0 )
		 {
			 sol ++;
			 dfs( i );
		 }
		 g << sol;
 }
 
 void citire()
 {
	 int i, x, y;
	 f >> n >> m;
	 for ( i = 1 ; i <= m ; ++ i )
	 {
		 f >> x >> y;
		 a[x].pb(y);
		 a[y].pb(x);
	 }
 }
 
 int main()
 {
	 citire();
	 rezolvare();
	 return 0;
 }