Cod sursa(job #765377)

Utilizator danalex97Dan H Alexandru danalex97 Data 7 iulie 2012 13:32:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

ifstream F("dfs.in");
ofstream G("dfs.out");

#define Mmax 200011
#define Nmax 100011

#define mark(i) ( Marked[i]=1 )
#define unmark(i) ( Marked[i]=0 )

vector<int> Leg[Mmax];
int Marked[Mmax];

int N,M,Comp;

void DF(int Nod)
{
	for ( register unsigned int i=0; i< Leg[Nod].size(); ++i)
		if ( !Marked[Leg[Nod][i]] )
		{
			Marked[Leg[Nod][i]]=1;
			DF(Leg[Nod][i]);
		}
}

int main()
{
	F>>N>>M;
	for (int i=1;i<=M;++i)
	{	
		int x,y;
		F>>x>>y;
		Leg[x].push_back(y);
		Leg[y].push_back(x);
	}
	for (int i=1;i<=N;++i)
		if ( !Marked[i] )
		{
			mark(i);
			++Comp;
			DF(i);
		}
	
	G<<Comp<<'\n';
}