Cod sursa(job #751630)

Utilizator danalex97Dan H Alexandru danalex97 Data 26 mai 2012 15:09:12
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include <fstream>
using namespace std;

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

#define Nmax 1011 

int N,M;
int Leg[Nmax][Nmax];
int Lung[Nmax];

int x,y;

void DF(int Nod,int Step)
{
	Lung[Nod]=Step;
	
	for (int i=1;i<=Leg[Nod][0];++i)
		if ( !Lung[ Leg[Nod][i] ] )
			DF(Leg[Nod][i],Step+1);
}

int main()
{
	F>>N>>M;
	for (int i=1;i<=M;++i)
	{
		F>>x>>y;
		Leg[x][++Leg[x][0]]=y;
		Leg[y][++Leg[y][0]]=x;
	}
	
	int C=0;
	for (int i=1;i<=N;++i)
		if ( !Lung[i] )
		{
			DF(i,1);
			++C;
		}
	
	G<<C<<'\n';
}