Cod sursa(job #1035674)

Utilizator roby2001Sirius roby2001 Data 18 noiembrie 2013 18:57:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
/*
          ~Keep It Simple!~
*/




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

using namespace std;

list<int> graph[100001];
int n,m,cnt;
bool viz[100001];

void dfs(int k)
{
	if(viz[k])
		return;
		viz[k] = 1;
	for(list<int>::iterator it = graph[k].begin();it!=graph[k].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);
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
	 {
		 if(!viz[i])
		 {
		 cnt++;
		 dfs(i);
		 }
	 }
		printf("%d ",cnt);
}