Cod sursa(job #766650)

Utilizator d.andreiDiaconeasa Andrei d.andrei Data 11 iulie 2012 19:25:37
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>

using namespace std;

#define nmax 101000

ifstream f("dfs.in");
ofstream g("dfs.out");

int N,M;
int viz[nmax];

class graf{
	
	typedef struct nod{
		
		int val;
		nod *urm;
	} *Pnod;
	Pnod p[nmax];
	
public:
	
	void add(int a, int b);
	friend istream &operator>>(istream&, graf&);
	void dfs(int nod);
	
};


void graf::add(int a, int b){
	
	nod * c=new nod;
	
	c->val=b;
	c->urm=p[a];
	p[a]=c;
}
	

istream &operator>>(istream &in, graf& G){
	
	int a,b;
	
	in>>N>>M;
	
	while(M--){
		
		in>>a>>b;
		
		G.add(a,b);
		G.add(b,a);
	}
	
	return in;
}

void graf::dfs(int nod){
	
	if (viz[nod])
		
		return ;
	
	viz[nod]=1;
	
	Pnod c;
	c=p[nod];
	
	while(c){
		
		if (!viz[c->val]){
			viz[c->val]=1;
			dfs(c->val);
		}
		
		c=c->urm;
	}
}

int main(){
	
	graf G;
	
	
	f>>G;
	
	int ans=0;
	for (int i=1;i<=N;++i)
		 if (!viz[i]){
			 ans++;
			 G.dfs(i);
		 }
		 
	g<<ans;	 
	
	return 0;
}