Cod sursa(job #413949)

Utilizator Addy.Adrian Draghici Addy. Data 9 martie 2010 14:45:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <stdio.h>
#include <vector>
#define Nmax 100050

using namespace std;

int L[Nmax], viz[Nmax], n, m, x, y, i, N;
vector <int> A[Nmax];

void DFS(int nod) {
	int i;
	
	viz[nod] = 1;
	for (i = 0; i < L[nod]; i++)
		if (!viz[A[nod][i]])
			DFS(A[nod][i]);
}

int main() {
	
	FILE *f = fopen("dfs.in", "r");
	FILE *g = fopen("dfs.out", "w");
	
	fscanf(f, "%d %d", &n, &m);
	for (i = 1; i <= m; i++) {
		fscanf(f, "%d %d", &x, &y);
		A[x].push_back(y);
		A[y].push_back(x);
	}
	
	for (i = 1; i <= n; i++)
		L[i] = A[i].size();
	
	for (i = 1; i <= n; i++)
		if (!viz[i]) {
			N++;
			DFS(i);
		}
	
	fprintf(g, "%d", N);
	
	return 0;
}