Cod sursa(job #1452332)

Utilizator Player1Player 1 Player1 Data 20 iunie 2015 16:23:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<stdio.h>

typedef struct nod
{
    int val;
    nod *dest;
} *gNode;

int N, M, result = 0;
int visited[100002] = {0};
gNode v[100002];
 
void add(gNode &destination, int value)
{
    gNode p;
    p = new nod;
    p -> val = value;
    p -> dest = destination;
    destination = p;
}

void DFS(int node)
{
	gNode p;
	visited[node] = 1;
	for(p = v[node]; p != NULL; p = p -> dest)
		if (visited[p-> val] == 0)
			DFS(p-> val);
}

int main(){
	int x, y, i;
	
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);

	scanf("%d %d ", &N, &M);
	
	for (i = 0; i < M ; i++){
		scanf("%d %d",&x,&y);
		add(v[x], y);
		add(v[y], x);
	}

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

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