Cod sursa(job #917522)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 17 martie 2013 23:43:33
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <string.h>
#include <iomanip>
using namespace std;


const string file = "dfs";

const string infile = file + ".in";
const string outfile = file + ".out";

#define MAXN 100001

int N;
int M;
int NrConex;

bool viz[MAXN];
vector<int> G[MAXN];


void citire()
{
	fstream fin(infile.c_str(), ios::in);

	fin >> N;
	fin >> M;

	for(int i = 0; i < M; i++)
	{
		int x, y;

		fin >> x >> y;

		G[x].push_back(y);
		G[y].push_back(x);
	}

	fin.close();
}


void dfs(int x)
{
	for(vector<int>::iterator itr = G[x].begin(); itr != G[x].end(); itr++)
	{
		if(viz[*itr] == false)
		{
			viz[*itr] = true;
			dfs(*itr);
		}
	}
}

void solve()
{
	for(int i = 0; i < N; i++)
	{
		if(viz[i] == false)
		{
			NrConex ++;
			viz[i] = true;
			dfs(i);
		}
	}
}


void afisare()
{
	fstream fout(outfile.c_str(), ios::out);

	fout << NrConex;

	fout.close();

}

int main()
{

	citire();
	solve();
	afisare();
}