Cod sursa(job #218961)

Utilizator tudalexTudorica Constantin Alexandru tudalex Data 4 noiembrie 2008 14:09:05
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include <stdio.h>
#include <vector>
using namespace std;
vector < int > v[100001];
int viz[100001];
int a, b, sol, n, m;
void df(int x)
{
	viz[x] = 1;
	for (int i = 0; i < v[x].size; ++ i)
		if(!viz[v[x][i]])
			df(v[x][i]);
}
int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; ++ i)
	{
		scanf("%d %d",&a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for (int i = 1; i <= n; ++ i)
		if (!viz[i])
			df(i),++sol;
	printf("%d\n",sol);
	return 0;
}