Cod sursa(job #1435867)

Utilizator gallexdAlex Gabor gallexd Data 14 mai 2015 18:31:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int N, M;
vector<int> graph[100100];
bool viz[100100];
int components;

void dfs(int n) {
	viz[n] = true;
	for (int i=0; i<graph[n].size(); ++i) {
		if (!viz[graph[n][i]]) {
			dfs(graph[n][i]);
		}
	}
}

int main () {

	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	int x, y;
	
	scanf("%d %d", &N, &M);
	for (;M;--M) {
		scanf("%d %d", &x, &y);
		graph[x].push_back(y);
		graph[y].push_back(x);
	}

	for (int i=1; i<=N; ++i) {
		if (!viz[i]) {
			dfs(i);
			++components;
		}
	}

	printf("%d", components);

	return 0;
}