Cod sursa(job #1761562)

Utilizator delia_ioanaCeapa Delia Ioana delia_ioana Data 22 septembrie 2016 15:44:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>
#include <vector>
#define maxn 100010

using namespace std;

int nums[maxn], n, m, x, y, sol = 0;
vector<vector<int> > adiacente(100001);
vector<bool> parcurs(100001, false);

void dfs(int nod) {
	parcurs[nod] = true;

	for (int i = 0; i < adiacente[nod].size(); i ++)
		 if (!parcurs[adiacente[nod][i]])
		 	dfs(adiacente[nod][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", &x, &y);
		adiacente[x].push_back(y);
		adiacente[y].push_back(x);
	}     

	for (int i = 1; i <= n; i ++) 
		if (!parcurs[i]) {
			dfs(i);
			sol ++;
		}

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

	return 0;
}