Cod sursa(job #1193840)

Utilizator pavlov.ionPavlov Ion pavlov.ion Data 1 iunie 2014 23:42:08
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<stdio.h>
#include<stdlib.h>

	struct nod{
  	int val;
  	nod *next;
  };
  nod**A;
int *viz,**C,N,M;
//instructiuni coada

void citire() {
	nod *nou;
	int i,x,y;
	scanf("%d %d",&N,&M);
	A=(nod**)malloc((N+1)*sizeof(nod*));
	for(i=1;i<=N;i++)
				A[i]=NULL;
		for(i=1;i<=M;i++) {
			scanf("%d %d",&x,&y);
			nou=new nod;
			nou->val=y;
			nou->next=A[x];
			A[x]=nou;
		}
	viz=(int*)calloc((N+1),sizeof(int));
}
void afgraf() {
	int i;
	nod *q;
	for(i=1;i<=N;i++) {
		q=A[i];
		while(q!=NULL){
			printf("%d ",q->val);
			q=q->next;
		}
		printf("\n");

	}
}
void dfs(int x) {
	nod *q;
	viz[x]=1;
	for(q=A[x];q!=NULL;q=q->next)
			if(!viz[q->val]) dfs(q->val);
}
int main() {
int i,k=0;
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	citire();
	for(i=1;i<=N;i++)
		if(!viz[i]) {
			k++;
			dfs(i);
		}
		printf("%d",k);
	fclose(stdin);
	fclose(stdout);
	return 0;
}