Cod sursa(job #150284)

Utilizator recviemAlexandru Pana recviem Data 6 martie 2008 20:15:52
Problema Parcurgere DFS - componente conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
//#include "stdafx.h"
#include "cstdio"
#include "vector"
#define fin  "dfs.in"
#define fout "dfs.out"
#define nM 100005
using namespace std;

	int n,m,nr=0,t[nM];
	vector<int> graf[nM];

void citire()
{
	freopen(fin,"r",stdin);
	scanf("%d %d",&n,&m);
	for (int i=0;i<m;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		graf[x].push_back(y);
		graf[y].push_back(x);
	}
	fclose(stdin);
}

void dfs(int x)
{
	for (vector<int>::iterator it = graf[x].begin(); it != graf[x].end(); it++)
		if (!t[*it])
		{
			t[*it]=1;
			dfs(*it);
		}
}

int main()
{
	citire();
	for (int i=0;i<n;i++)
		if (!t[i])
		{
			dfs(i);
			nr++;
		}
	freopen(fout,"w",stdout);
	printf("%d",nr);
	fclose(stdout);
	return 0;
}