Cod sursa(job #361574)

Utilizator dexter_dexMutascu Adrian - Dragos dexter_dex Data 5 noiembrie 2009 21:34:29
Problema Parcurgere DFS - componente conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<fstream.h>
#include<vector>
#define Nmax 100010

using namespace std;

vector <int> A[Nmax];
int c, n, m, i, x, y, ok, start;
int viz[Nmax], Lg[Nmax];

void dfs(int k){
	
	int j;
	viz[k] = c;
	for (j = 0 ; j <= Lg[k] - 1 ; j++)		
		if (viz[A[k][j]] == 0)
			dfs(A[k][j]);
	
}
	

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);
	}
	
	ok = 1;
	
	for (i = 1 ; i <= n ; i++)
		Lg[i] = A[i].size();
	
	while (ok){
		
		ok = 0;
		for (i = 1 ; i <= n ; i++)
			if (viz[i] == 0) {
				ok = 1;
				c++;
				start = i;
				break;
			}
		
		dfs(start);
		
	}
	
	fprintf(g, "%d", c);
	
	fclose(f);
	fclose(g);
	return 0;
}