Cod sursa(job #1620277)

Utilizator mariusadamMarius Adam mariusadam Data 28 februarie 2016 22:54:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 100001
typedef struct node{
	int info;
	struct node *next;
}node;

node *G[NMAX];
int  viz[NMAX];

void dfs(int nod){
	viz[nod] = 1;
	node *p = NULL;
	for(p = G[nod]; p != NULL; p = p->next)
		if(!viz[p->info])
			dfs(p->info);
}

int main(){
	int n, m, i, j;
	FILE *fpi = freopen("dfs.in", "r", stdin);
	scanf("%d %d", &n, &m);
	for(; m; m--){
		scanf("%d %d", &i, &j);
		node *p = (node*)malloc(sizeof(node));
		p->next = G[i];
		p->info = j;
		G[i] = p;
		node *p2 = (node*)malloc(sizeof(node));
		p2->next = G[j];
		p2->info = i;
		G[j] = p2;
	}
	fclose(fpi);
	int cnt = 0;
	for (i = 1; i <= n; i++)
		if(!viz[i]){
			dfs(i);
			cnt++;
		}
	FILE *fpo = freopen("dfs.out", "w", stdout);
	printf("%d", cnt);
	fclose(fpo);
	for(i = 1; i <= n; i++){
		node *p = NULL;
		for(p = G[i]; p != NULL; p = p->next)
			free(p);
	}
	return 0;
}