Cod sursa(job #1039247)

Utilizator thesilverhand13FII Florea Toma Eduard thesilverhand13 Data 22 noiembrie 2013 18:29:55
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
 
 # include <fstream>
 # include <cstring>
 # include <vector>
 # include <algorithm>
 
 # define dim 100005
 
 using namespace std;
 
 vector <int> A[dim];
 int viz[dim];
 
 int N, M;
 int sol;
 
 
 ifstream f("dfs.in");
 ofstream g("dfs.out");
 
 void citire()
 {
	 int i, X, Y;
	 
	 f >> N >> M;
	 for(i = 1; i <= M; i++)
	 {
		 f >> X >> Y;
		 A[X].push_back(Y);
		 A[Y].push_back(X);
	 }
 }
 
 void parc(int x)
 {
	 int i;
	 
	 viz[x] = 1;
	 
	 for(i = 1; i < A[x].size(); ++i)
		 if (viz[A[x][i]] == 0 )
			 parc( A[x][i] );
 }
 
 int main()
 {
	 int i;
	 citire();
	 for(i = 1; i <= M; ++i)
		 if (viz[i] == 0)
			 parc( i ), sol++;
	 g << sol;
	 return 0;
 }