Cod sursa(job #649767)

Utilizator FIIAndCocRotAndrei Alexandra FIIAndCocRot Data 16 decembrie 2011 18:01:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.07 kb
#include<stdio.h>
#include<stdlib.h>

#define MAX 100003

FILE *f, *g;

int N, M, viz[MAX], index, nr_comp;


typedef struct Node 
{	int info; 
	struct Node *next;
} Node;
Node *a[MAX];

void file_open ()
{	f=fopen("dfs.in", "r");
	g=fopen("dfs.out", "w");
}


void file_close ()
{	fclose (f);
	fclose(g);
}

int add (int n1, int n2)
{	Node *ptr;
	if(!(ptr=(Node*)malloc(sizeof(Node))))
		return 0;
	ptr->info=n2;
	ptr->next=a[n1];
	a[n1]=ptr;
	return 1;
}

void read_node ()
{ 	int n1, n2;
	for(index=0; index<M; index++)
	{fscanf(f,"%d%d", &n1, &n2);
	 if(!(add(n1,n2)))
		{printf("eroare");
		 return ;
		}
	 if(!(add(n2,n1)))
		{printf("eroare");
		return;	
		}
	}
}

void DFS(int S)
{	Node *p;
	viz[S]=1;
   	for(p=a[S]; p!=NULL; p=p->next)
     		if(viz[p->info]==0)
		     DFS(p->info);
			
		
	

}	

int main ()
{	file_open();
	fscanf(f,"%d %d", & N, &M);
	read_node();
	for(index=1;index<=N;index++)
	if(viz[index]==0)
		{nr_comp++;
		DFS(index);}
	fprintf(g, "%d ", nr_comp);
	
	file_close();
	return 0;
}