Cod sursa(job #651312)

Utilizator vladbaesuVlad Baesu vladbaesu Data 20 decembrie 2011 07:30:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.78 kb
#include<stdio.h>
#define MAXNOD 100005

typedef struct Nod{int info; struct Nod *next;} Nod;
Nod *G[MAXNOD];
int vizitat[MAXNOD],N,M;

void dfs(int x)
{
	Nod *p;
	vizitat[x]=1;
	for(p=G[x];p;p=p->next) if(!vizitat[p->info]) dfs(p->info);    
}


int main()
{
	FILE *intrare,*iesire;
	int i,x,y,compcon=0;

	intrare=fopen("dfs.in","r");
	fscanf(intrare,"%d %d",&N,&M);
	for(i=1;i<=M;i++)
	 {
	  Nod *p,*q;
	  fscanf(intrare,"%d %d",&x,&y);
	  if(!(p=(Nod*)malloc(sizeof(Nod)))) return 1;
	  p->info=y;
	  p->next=G[x];
	  G[x]=p;
	  if(!(q=(Nod*)malloc(sizeof(Nod)))) return 1;
	  q->info=x;
	  q->next=G[y];
	  G[y]=q;
	 }
	iesire=fopen("dfs.out","w");
	for(i=1;i<=N;i++) if(vizitat[i]==0) { compcon++; dfs(i); }

	fprintf(iesire,"%d",compcon);

	fclose(intrare);fclose(iesire);
	return 0;    
}