Cod sursa(job #484679)

Utilizator edward_alexStanciu Alexandru Marian edward_alex Data 15 septembrie 2010 11:32:56
Problema Parcurgere DFS - componente conexe Scor 15
Compilator c Status done
Runda Arhiva educationala Marime 0.85 kb
#include<stdio.h>
#include<stdlib.h>

typedef struct nod{
	int info;
	struct nod *next;
}nod;

nod *a[1000009];

void adauga(int x,nod **u){
    nod *nou = (nod*)malloc(sizeof(nod));
    nod *ultim = *u;
    nou->info = x;
    nou->next = ultim;
    *u = nou;
}

void dfs(int x,int *v){
	int y;
	nod *u;
	v[x] = 1;
	for(u = a[x];u != NULL;u = u->next){
		y = u->info;
		if(v[y] == 0){
			dfs(y,v);
		}
	}
}

int main(){
	FILE *f,*g;
	f = fopen("dfs.in","r");
	g = fopen("dfs.out","w");
	int n,m,i,k1,k2;
	fscanf(f,"%d%d",&n,&m);
	for(i = 1;i <= n;i++)
		a[i] = NULL;
	for(i = 0;i < m;i++){
		fscanf(f,"%d%d",&k1,&k2);
		adauga(k2,&a[k1]);
	}
	int k = 0;
	int *v = (int*)calloc((n + 1),sizeof(int));
	for(i = 1;i <= n;i++)
		if(v[i] == 0){
			dfs(i,v);
			k++;
		}
	fprintf(g,"%d\n",k);
	free(v);
	fclose(f);
	fclose(g);
	return 0;
}