Mai intai trebuie sa te autentifici.

Cod sursa(job #361298)

Utilizator BaduBadu Badu Badu Data 4 noiembrie 2009 16:08:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<stdio.h>
#include<vector>
#define max 100001
#define pb push_back

using namespace std;

vector< vector<int> > a(max);
short v[max];
int n,m,nr,k;

void data(){

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

	int x,y;
	fscanf(f,"%d%d",&n,&m);
	for(; m-- ;){
		fscanf(f,"%d%d",&x,&y);
		a[x].pb(y);
		a[y].pb(x);
	}
}
		
void dfs(int nod){


	int i;
	v[nod]=1;

	for(i=0; i<a[nod].size(); i++)
		if( !v[a[ nod ][ i ]] ) dfs( a[ nod ][ i ] );

}

int main(){

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

	data();
	int i;
	for(i=1;i<=n;i++)
		if(!v[i]) {nr++;dfs(i);}

	fprintf(g,"%d",nr);

	return 0;
}