Cod sursa(job #1345632)

Utilizator gerd13David Gergely gerd13 Data 17 februarie 2015 19:31:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <vector>
#include <algorithm>

#define x first
#define y second
#define mp make_pair
#define pb push_back


using namespace std ;




	const int NMAX =  200005 ;
	const int INF = 0x3f3f3f3f ;



	ifstream fin("dfs.in") ;
	ofstream fout("dfs.out") ;

	int N, M ;
	bool vis[NMAX] ;
	vector<int> V[NMAX];

	int cnt = 0 ;

	inline void READ() {
		fin >> N >> M ;

		for(int i = 1 ; i <= M ; ++ i)
		{
			int X, Y ;

			fin >> X >> Y ;
			V[X].pb(Y) ;
			V[Y].pb(X) ;
		}
	}

	 void DFS(int nod)
	{
		vis[nod] = 1 ;

		for(int i = 0 ; i < V[nod].size() ; ++ i)
			if(!vis[V[nod][i]])
				DFS(V[nod][i]) ;

	}

int main()
{

	READ() ;


	for(int i = 1 ; i <= N ; ++ i)
	{
		if(!vis[i])
		{
			++ cnt ;
			DFS(i) ;
		}
	}


	fout << cnt << '\n' ;
	fin.close() ;
	fout.close() ;
	return  0 ;
}