Cod sursa(job #161509)

Utilizator vlad2179Popescu Vlad Alexandru vlad2179 Data 18 martie 2008 12:34:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>
#define INPUT "dfs.in"
#define OUTPUT "dfs.out"
int ap[100005],n,m,componente;

typedef struct nod {
	int x;
	nod *a;
} *pNod;
pNod g[100005];

void dfs(int nod){
	 pNod p;
	ap[nod]=1;
	 for(p = g[nod] ; p != NULL ; p = p -> a )
		  if( ! ap [ p -> x ] ) dfs ( p -> x );
}

void adauga(pNod &z, int v){
	 pNod q;
	 q=new nod;
	 q -> x = v;
	 q -> a = z ; 
	 z = q;
}

void date(){int a,b;
	FILE *fin=fopen(INPUT,"rt");
	fscanf(fin,"%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		fscanf(fin,"%d %d",&a,&b);
		adauga(g[a],b);
		adauga(g[b],a);
	}
}

int main(){
	FILE *fout=fopen(OUTPUT,"wt");
	date();
	for(int i=1;i<=n;i++) if(!ap[i]) {componente++;dfs(i);}
	fprintf(fout,"%d",componente);
	return 0;
}