Cod sursa(job #917529)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 17 martie 2013 23:51:39
Problema Parcurgere DFS - componente conexe Scor 100
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 - 1].push_back(y - 1);
		G[y - 1].push_back(x - 1);
	}

	fin.close();
}


void dfs(int x)
{
	if(viz[x] == true)
		return;
	viz[x] = true;

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

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


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

	fout << NrConex << "\n";

	fout.close();

}

int main()
{

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