Cod sursa(job #677385)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 10 februarie 2012 08:46:57
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <vector>

using namespace std;

vector <int> G[100005];
int L[100005];
int N, M,NCC;
char V[100005];

void Read ()
{
	ifstream fin ("sate.in");
	int i,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 ()
{int i;
	ofstream fout ("sate.out");
	fout << NCC<< "\n";
	/*	for(i=0;i<NCC-1;i++)
			fout<<L[i]<<" "<<L[i+1]<<"\n";*/
	fout.close ();
}

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

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