Cod sursa(job #513103)

Utilizator BeRReTLiviu P. BeRReT Data 15 decembrie 2010 08:49:47
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.47 kb
#include <iostream.h>
#include <fstream.h>
#define DIM 1002
int a[DIM][DIM], N, M, nr1, nr2, i, nc, v[DIM]; 
ifstream f("dfs.in");
ofstream g("dfs.out");
void df(int, int);
int main (){
	f>>N>>M;
	for(i=1;i<=M;i++){
		f>>nr1>>nr2;
		a[nr1][nr2]=a[nr2][nr1]=1;}
	nc=0;
	for(i=1;i<=N;i++)
		if(v[i]==0){
			nc++;
			df(i,nc);
		}
	g<<nc;
	f.close();
	return 0;
}
void df(int i, int k){
	v[i]=k;
	for(int p=1;p<=N;p++)
		if(a[i][p]==1 && v[p]==0)
			df(p,k);
}