Cod sursa(job #503145)

Utilizator bmaticanBogdan-Alexandru Matican bmatican Data 21 noiembrie 2010 19:41:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<stdio.h>
#include<stdlib.h>

int mask[100001];
struct list* edges[100001];
int N, M, count = 0;

struct list {
	int data;
	struct list* next;
};

void DFS(int x) {
		if(mask[x] == 0) {
			count++;
			mask[x] = count;
		}
		struct list *p = edges[x];
		while(p != NULL) {
			if(mask[p->data] == 0) {
				mask[p->data] = count;
				DFS(p->data);
			}
			p = p->next;
		}
}

int main() {
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	int i;
	
	scanf("%d%d", &N, &M);
	for(i = 1; i<=N; i++) {
		mask[i] = count;
		edges[i] = NULL;
	}
	int x,y;
	for(i = 1; i<=M; i++) {
		struct list *a, *b;
		scanf("%d%d", &x, &y);
		
		a = (struct list*)malloc(sizeof(struct list));
		a->data = y;
		a->next = edges[x];
		edges[x] = a;
		
		b = (struct list*)malloc(sizeof(struct list));
		b->data = x;
		b->next = edges[y];
		edges[y] = b;
	}

	for(i = 1; i<=N; i++) {
		DFS(i);
	}
	printf("%d\n", count);
	return 0;
}