Cod sursa(job #981191)

Utilizator petrutsxMihaela Petruta Gaman petrutsx Data 6 august 2013 15:46:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<stdio.h>
#define NMAX 100001

struct Node{
	int value;
	struct Node *next;
};

struct Node *L[NMAX];
int N, M, visited[NMAX], conexe = 0;

int min(int a, int b){
	if(a < b)
		return a;
	return b;
}

void read(FILE *pf){
	int i, u, v;
	struct Node *p, *q;
	fscanf(pf, "%d %d", &N, &M);
	if(M >= 200000)
		M = min(200000, N * (N + 1) / 2);
	
	for(i = 1; i <= M; i++){
		fscanf(pf, "%d %d", &u, &v);
		p = new  Node;
		p->value = v;
		p->next = L[u];
		L[u] = p;
		q = new Node;
		q->value = u;
		q->next = L[v];
		L[v] = q;
	}
}

void DFS(int u){
	int v;
	struct Node *p;
	visited[u] = 1;
	p = L[u];
	
	while(p != NULL){
		v = p->value;
		if(visited[v] == 0)
			DFS(v);
		p = p->next;
	}
}

int main(){
	int i;
	FILE *pf, *pg;
	pf = fopen("dfs.in", "r");
	pg = fopen("dfs.out", "w");

	read(pf);
	for(i = 1; i <= N; i++)
		if(visited[i] == 0){
			DFS(i);
			conexe++;
		}

	fprintf(pg, "%d", conexe);

	fclose(pf);
	fclose(pg);
	
	return 0;
}