Cod sursa(job #539862)

Utilizator fgravilaGravila Felix fgravila Data 23 februarie 2011 13:56:09
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<fstream>
using namespace std;

int m,n,a[200000][2],viz[100000];

void citire(){
	ifstream in("dfs.in");
	in>>n>>m;
	int i;
	for(i=0;i<n;i++)viz[i]=-1;
	for(i=0;i<m;i++)in>>a[i][0]>>a[i][1];
}

void bf(int nod){
	int i;
	for(i=0;i<m;i++){
		if(a[i][0]==nod and viz[a[i][1]]==-1){
			viz[a[i][1]]=1;
			bf(a[i][1]);
		}
		if(a[i][1]==nod and viz[a[i][0]]==-1){
			viz[a[i][0]]=1;
			bf(a[i][0]);
		}
	}
}

int proces(){
	int i,nr=0;
	for(i=0;i<n;i++)
		if(viz[i]==-1){
			bf(i);
			nr++;
		}
	return nr;
}

int main(){
	citire();
	ofstream out("dfs.out");
	out<<proces();
	out.close();
	return 0;
}