Cod sursa(job #253366)

Utilizator willliIonel Bratianu willli Data 5 februarie 2009 18:28:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.47 kb
#include <stdio.h>
#include <stdlib.h>
#define in "dfs.in"
#define out "dfs.out"
#define MAX 100001

struct edge
{
	long node;
	struct edge *next;
};

struct node
{
	int visited;
	struct edge *node;
};

struct node graph[MAX];
long n, nr = 0;

//add a new edge to graph
void add_edge(long x, long y)
{	
	//create a new node
	struct edge *new_edge;	
	if ((new_edge = (struct edge *)malloc(sizeof(struct edge))) == NULL)
	{
		printf("Not enoug memory\n");
		exit(-1);
	}	
	new_edge->node = y;
	new_edge->next = graph[x].node;
	//add a new tail edge
	graph[x].node = new_edge;
}

void read_file()
{
	FILE *fin;
	long int x, y, m, i;
	
	if ((fin = fopen(in, "r")) == NULL)
	{
		printf("Eroare \n");
		exit(-1);
	}
	//read the two nodes
	fscanf(fin, "%ld%ld", &n, &m);
	for (i = 1; i <=n ; i++)
	{
		graph[i].visited = 0;
		graph[i].node = NULL;
	}
	for (i = 0; i < m; i++)
	{
		fscanf(fin, "%ld%ld", &x, &y);		
		//add a new node in graph
		add_edge(x, y);
		add_edge(y, x);
	}
	fclose(fin);
}

void dfs(long node)
{
	struct edge *t;
	
	graph[node].visited = 1;
	
	//add the unvisited nodes to queue
	for (t = graph[node].node; t != NULL; t = t->next)
	{
		if (graph[t->node].visited == 0)
		{
			dfs(t->node);
		}
	}
}

void solve()
{
	long i;

	for (i = 1 ; i <= n; i++)
		if (graph[i].visited == 0)
		{
			dfs(i);
			nr++;
		}
		
}

void print_file()
{
	FILE *fout;
	fout = fopen(out, "w");
	fprintf(fout, "%ld", nr);
	fclose(fout);
}


int main()
{
	read_file();
	
	solve();
	
	print_file();	

	return 0;
}