Cod sursa(job #513101)

Utilizator MieluNegruGabriel Bila MieluNegru Data 15 decembrie 2010 08:49:24
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.49 kb
#include <iostream.h>
#include <fstream.h>

char a[1000][1000]; 
int v[1000], N,M,nr1,nr2,i,nc;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

void df(int, int);

int main() {
	fin>>N>>M;
	for (i=1;i<=M;i++) {
		fin>>nr1>>nr2;
		a[nr1][nr2]=a[nr2][nr1]=1;
	}
	fin.close();
	
	for (i=1;i<=N;i++)
		if (v[i]==0) {
			nc++;
			df(i,nc);
		}			
	fout<<nc;
	fout.close();
}

void df(int x, int k) {
	v[x]=k;
	for (int i=1;i<=N;i++)
		if (a[x][i]==1 && v[i]==0)
			df(i,k);
}