Cod sursa(job #530871)

Utilizator Dana_2011D.M.Florescu Dana_2011 Data 8 februarie 2011 16:33:38
Problema Parcurgere DFS - componente conexe Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 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 init(){
	for(int i=1;i<=n;i++) v[i]=0;
	return 0;
}
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 main(){
	f>>n>>m;
	while(f>>i>>j){
       p=new nod;
       p->nr=i;
       p->ante=l[j];
	   l[j]=p;
	}
	ifstream f2("dfs.in");
	f2>>n>>m;
	while(f2>>i>>j){
		p=new nod;
		p->nr=j;
		p->ante=l[i];
		l[i]=p;
	}
    mm=0;
	for(i=1;i<=n;i++){
  		  if(!v[i]){
			  mm++;
	        df(i);
		  }
	}
	g<<mm<<"\n";
	f2.close();
	f.close();
	g.close();
	return 0;
}