Cod sursa(job #530898)

Utilizator Dana_2011D.M.Florescu Dana_2011 Data 8 februarie 2011 16:55:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<fstream.h>
#include<stdio.h>
ifstream f("dfs.in");
ofstream g("dfs.out");
typedef struct nod{
	int nr;
	nod *ante;
};
nod *l[100000],*p;
long n,m,i,j,mm,max;
int v[100000];
int df(int k){
	nod *q;
	q=l[k];
	v[k]=1;
	while(q){
		if(!v[q->nr])
			df(q->nr);
		q=q->ante;
	}
	return 0;
}
int insert(nod *&p, int x) {
    nod* q;
    q= new nod();
    q->ante = p;
    q->nr = x;
    p = q;
	return 0;
}
int main(){
	f>>n>>m;
	while(f>>i>>j){
       insert(l[i],j);
	   insert(l[j],i);
	}
    mm=0;
	for(i=1;i<=n;i++){
  		  if(!v[i]){
			  mm++;
	        df(i);
		  }
	}
	g<<mm<<"\n";
	f.close();
	g.close();
	return 0;
}