Cod sursa(job #365833)

Utilizator titusuTitus C titusu Data 20 noiembrie 2009 00:33:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#define NMAX 100001
using namespace std;
struct nod{
	int info;
	nod * next;
};

nod * a[NMAX];
int v[NMAX], n , nrc;

void dfs(int start, int culoare){
	v[start]=culoare;
	for(nod * p  = a[start]; p ;p = p ->next)
		if(v[p->info] == 0){
			dfs(p->info, culoare);
		}
}
void read(){
	ifstream fin("dfs.in");
	int m;
	fin>>n>>m;
	for(int i =1;i<=n;i++)
		a[i] = NULL;
	for( ; m ; m--){
		int i,j;
		fin>>i>>j;
		nod * t = new nod;
		t->info=j;
		t->next = a[i];
		a[i] = t;
		t=new nod; t->info=i;
		t->next = a[j];
		a[j] = t;
	}
}

int main(){
	read();
	for(int i = 1 ;i <= n ; i++)
		if(v[i] == 0)
			dfs(i, ++nrc);
	ofstream fout("dfs.out");
	fout<<nrc;
	fout.close();
	return 0;
}