Cod sursa(job #841859)

Utilizator Brz_VladBrezae Vlad Brz_Vlad Data 25 decembrie 2012 11:17:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
#include <stdlib.h>

////////////// LIST ///////////////////

typedef struct tagNode
{
	int vecin;
	struct tagNode *next;
}Node;

typedef struct tagList
{
	Node* start;
}List;

void initList(List *list)
{
	list->start = NULL;	
}

void addList(List *list, int vecin)
{
    Node *new = malloc(sizeof(Node));
    new->next = list->start;
    new->vecin = vecin;
    list->start = new;
}

////////////////////////////////////////


#define MAXN 100001

int M,N;
int visited[MAXN];
int componente;

List vecini[MAXN];

int dfs(int node)
{
	visited[node] = 1;
	
	Node *q = vecini[node].start;
	while( q != NULL){
		int vecin = q->vecin;
		if( !visited[vecin] ){
			dfs(vecin);
		}
		q=q->next;
	}	
}

int main(int argc, char* argv[])
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
	scanf("%d %d",&N,&M);
	
	int i,a,b;
	
	for(i=1;i<=N;i++){
		initList(&vecini[i]);
	}
	
	for(i=0;i<M;i++){
		scanf("%d %d",&a,&b);
		addList(&vecini[a],b);
		addList(&vecini[b],a);
	}
	
	for(i=1;i<=N;i++){
		if( !visited[i] ){
			componente++;
			dfs(i);
		}
	}

	printf("%d",componente);
	
	return 0;
}