Cod sursa(job #656769)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 5 ianuarie 2012 10:56:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<iostream>
#include<stdio.h>
#include<vector>

using namespace std;

#define N_MAX 100001

vector <int> a[N_MAX];
bool ut[N_MAX];
int x, y, nr;
int i, n, m;

void dfs(int nod)
{
	ut[nod] = true;
	vector <int> ::iterator it;
	for(it = a[nod].begin(); it != a[nod].end(); it ++)
		if(!ut[*it])
			dfs(*it);
}
int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
	scanf("%d %d", &n, &m);
	for(i = 1; i <= m; i ++)
	{
		scanf("%d %d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for(i = 1; i <= n; i ++)
		if(!ut[i])
		{
			nr ++;
			dfs(i);
		}
	printf("%d\n", nr);
	return 0;
}