Cod sursa(job #591929)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 25 mai 2011 21:55:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector <long> G[100005];
long N, NCC;
bool V[100005];

void Read ()
{
	ifstream fin ("dfs.in");
	long i, M, X, Y;
	fin >> N >> M;
	for (i=0; i<M; i++)
	{
		fin >> X >> Y;
		G[X].push_back (Y);
		G[Y].push_back (X);
	}
	fin.close ();
}

void Type ()
{
	ofstream fout ("dfs.out");
	fout << NCC << "\n";
	fout.close ();
}

void DFS (long X)
{
	unsigned long i;
	V[X]=true;
	for (i=0; i<G[X].size (); i++)
	{
		if (V[G[X][i]]==false)
		{
			DFS (G[X][i]);
		}
	}
}

int main ()
{
	long i;
	Read ();
	for (i=1; i<=N; i++)
	{
		if (V[i]==false)
		{
			NCC++;
			DFS (i);
		}
	}
	Type ();
	return 0;
}