Cod sursa(job #156481)

Utilizator snaked31Stanica Andrei snaked31 Data 12 martie 2008 16:21:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

#define nm 100010
#define pb push_back

int n, m, i, sol, x, y;
int u[nm];
vector <int> v[nm];


void read()

{
	scanf("%d %d ", &n, &m);
	for (i=1; i<=m; ++i)
	{
		scanf("%d %d ", &x, &y);
		v[x].pb(y);
		v[y].pb(x);
	}
}


void dfs(int p)

{
	u[p] = 1;
	int i;
	for (i=0; i<v[p].size(); ++i)
	{
		if (u[v[p][i]] == 0)
			dfs(v[p][i]);
	}
}


void solve()

{
	sol = 0;
	for (i=1; i<=n; ++i)
	{
		if (u[i] == 0)
		{
			++sol;
			dfs(i);
		}
	}
}


void write()

{
	printf("%d\n", sol);
}


int main()

{
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out","w",stdout);
	
	read();
	solve();
	write();

	return 0;
}