Cod sursa(job #146288)

Utilizator filipbFilip Cristian Buruiana filipb Data 1 martie 2008 15:18:55
Problema Parcurgere DFS - componente conexe Scor Ascuns
Compilator cpp Status done
Runda Marime 0.78 kb
#include <stdio.h>
#include <assert.h>
#include <vector>

using namespace std;

#define ll long long
#define minim(a, b) ((a < b) ? a : b)

int N, M, uz[100005], conex;
vector<int> G[100005];

void df(int nod)
{
	int i, sz, x;

	uz[nod] = 1;
	for (sz = G[nod].size(), i = 0; i < sz; ++i)
		if (!uz[x = G[nod][i]])
			df(x);
}

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

	scanf("%d %d", &N, &M);
	assert(1 <= N && N <= 100000);
	assert(0 <= M && M <= minim((ll)N * (N+1)/2, 200000));
	for (; M; --M)
	{
		scanf("%d %d", &i, &j);
		assert(1 <= i && i <= N);
		assert(1 <= j && j <= N);
		G[i].push_back(j);
		G[j].push_back(i);	
	}
	
	for (i = 1; i <= N; i++)
		if (!uz[i])
		{
			++conex;
			df(i);
		}
	
	printf("%d\n", conex);
	
	return 0;
}