Cod sursa(job #513834)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 17 decembrie 2010 08:04:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<stdio.h>
#include<vector>
using namespace std;

FILE*f=fopen("dfs.in","r");
FILE*g=fopen("dfs.out","w");

int M,i,N,K,x,y;

char Viz[100005];

vector<int>W[100005];

void dfs (int nod){
	
	Viz[nod] = 1;
	int C[100005];
	int p = 1; int u = 1;
	C[1] = nod;
	vector<int>::iterator itt;
	while ( p <= u ) {
		
		for ( itt = W[C[p]].begin() ; itt != W[C[p]].end() ; ++itt ){
			if ( !Viz[ *itt ] ){
				Viz[ *itt ] = 1;
				C[++u] = *itt;
			}
			
		}
		
		++p;
	}
	
	
}


int main ( ) {
	
	fscanf(f,"%d %d",&N,&M);
	
	for ( i = 1 ; i <= M ; ++i ){
		fscanf(f,"%d %d",&x,&y);
		W[x].push_back(y);
		W[y].push_back(x);
	}
	
	for ( i = 1 ; i <= N ; ++i ){
		if ( !Viz[i] ){
			++K;
			dfs(i);
		}
	}

	fprintf(g,"%d\n",K);
	
	fclose(f);
	fclose(g);
	
	return 0;
}