Cod sursa(job #233167)

Utilizator cvicentiuCiorbaru Vicentiu Marian cvicentiu Data 16 decembrie 2008 23:09:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
int n,m;
int nr;
struct nod {
		int x;
		nod *urm;
};
bool viz[200001];
nod *vf[100001];

using namespace std;
void adauga(int ex1,int ex2){
	nod *p=new nod;
	nod *q=new nod;
	p->urm = vf[ex1];
	p->x = ex2;
	vf[ex1]=p;
	q->urm = vf[ex2];
	q->x = ex1;
	vf[ex2]=q;
}

void citire(){
	int ex1,ex2;
	fstream fin("dfs.in",ios::in);
	fin>>n>>m;
	for (int i=1;i<=m;i++){
		fin>>ex1>>ex2;
		adauga(ex1,ex2);
	}
	fin.close();
}

void dfs(int x){
	nod *p;
	viz[x]=true;
	for (p=vf[x];p!=NULL;p=p->urm){
		if (viz[p->x]==false)
			dfs(p->x);
	}
}

int main(){
	fstream fout("dfs.out",ios::out);
	citire();
	for (int i=1;i<=n;i++){
		if (viz[i]==false){
			nr++;
			dfs(i);
		}
	}
	fout<<nr;
	fout.close();
return 0;
}