Cod sursa(job #554156)

Utilizator Vitalia.GenVitalia Andrei Vitalia.Gen Data 14 martie 2011 17:29:46
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<stdio.h>
#include<vector>
#define NMAX 100001
#define input "dfs.in"
#define output "dfs.out"

using namespace std;
vector<int> G[NMAX];
int x,y,n,m,nr;
bool v[NMAX];

void DFS(int nod)
{
	v[nod]=true;
	for(int i=0;i<G[nod].size();i++)
	{
		int y=G[nod][i];
		if(!v[y]
			DFS(y);
	}
}
void open()
{
	freopen(input,"r", stdin);
	freopen(output,"w",stdout);
}
void read()
{
	scanf("%d%d",%n%m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
}
void count()
{
	for(int i=1;i<=n;i++)
		if(!v[i])
		{
			nr++;
			DFS(i);
		}
		printf("%d\n",nr);
}
int main()
{
	open();
	read();
	count();
	return 0;
}