Cod sursa(job #705908)

Utilizator andrici_cezarAndrici Cezar andrici_cezar Data 5 martie 2012 10:09:36
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <cstdio>
#include <queue>
#include <vector>

#define maxn 100001

using namespace std;
vector <long> A[maxn];

long x, y, N, K, G[maxn], nr, i;
bool viz[maxn];
 
void dfs(long nod) {
	++nr;
	viz[nod] = true;
	for (long i = 0; i < G[nod]; ++i) {
		if (!viz[ A[nod][i] ]) {
			dfs(A[nod][i]);
		}
	}
}

int main() {
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
		scanf("%ld %ld", &N, &K);
		
		for (i = 1; i <= K; ++i) {
			scanf("%ld %ld", &x, &y);
			A[x].push_back(y);
			A[y].push_back(x);
		}
		
		for (i = 1; i <= N; ++i) {
			G[i] = A[i].size();
		}
		
		nr = 0;
		dfs(1);
		
		printf("%ld\n", nr);
	
	return 0;
}