Cod sursa(job #220381)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 10 noiembrie 2008 17:36:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<stdio.h>
#define N 100007
#define M 200007
bool viz[N];
int *a[N];
int n,m;

struct muchie{
	int x,y;
};
muchie v[M];

void citire(){
	int x,y;
	int d[N]={0};
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&x,&y);
		++d[x];
		++d[y];
		v[i].x=x;
		v[i].y=y;
	}
	for(int i=1;i<=n;++i){
		a[i]=new int[d[i]+1];
		a[i][0]=0;
	}
	for(int i=1;i<=m;++i){
		x=v[i].x;
		y=v[i].y;
		a[x][++a[x][0]]=y;
		a[y][++a[y][0]]=x;
	}
	//for(int i=1;i<=n;++i)
}

void dfs(int x){
	viz[x]=true;
	for(int i=1;i<=a[x][0];++i){
		int y=a[x][i];
		if(!viz[y])
			dfs(y);
	}
}

int main(){
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	citire();
	int nr=0;
	for(int i=1;i<=n;++i)
		if(!viz[i]){
			dfs(i);
			++nr;
		}
	printf("%d\n",nr);
	fclose(stdin);
	fclose(stdout);
	return 0;
}