Cod sursa(job #1145647)

Utilizator SilverGSilver Gains SilverG Data 18 martie 2014 12:52:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
/*
    Keep It Simple!
*/

#include<stdio.h>
#include<list>

using namespace std;

#define MaxN 100001

int N,M,Conex_Groups_Number;

list<int> G[MaxN];

bool viz[MaxN];

void DFS(int node)
{
	viz[node] = 1;
	for(list<int>::iterator it = G[node].begin(); it!=G[node].end(); it++)
		if(!viz[*it])
			DFS(*it);
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);

	scanf("%d%d",&N,&M);

	int x,y;

	for(int i=1; i<=M; i++)
	  {
	  	scanf("%d%d",&x,&y);
	  	G[x].push_back(y);
	  	G[y].push_back(x);
	  }

	for(int i=1;i<=N;i++)
	{
		if(!viz[i])
		{
			Conex_Groups_Number++;
			DFS(i);
		}
	}

	printf("%d",Conex_Groups_Number);
}