Cod sursa(job #195274)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 17 iunie 2008 11:44:06
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<stdio.h>
#define N 100000
struct muchie{
	int x,y;
};
muchie v[N];
int *a[N];
bool viz[N];
int n,m,d[N];
void citire(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i){
		scanf("%d%d",&v[i].x,&v[i].y);
		++d[v[i].x];
		++d[v[i].y];
	}
	for(int i=1;i<=n;++i){
		a[i]=new int[d[i]+1];
		a[i][0]=0;
	}
	for(int i=0;i<m;++i){
		a[v[i].x][++a[v[i].x][0]]=v[i].y;
		a[v[i].y][++a[v[i].y][0]]=v[i].x;
	}
}
void df(int x){
	int y;
	viz[x]=true;
	for(int i=1;i<=a[x][0];++i){
		y=a[x][i];
		if(!viz[y])
			df(y);
	}
}
int main(){
	int k=0,i;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	citire();
	for(i=1;i<=n;++i)
		viz[i]=false;
	for(i=1;i<=n;++i)
		if(viz[i]==false){
			++k;
			df(i);
		}
	printf("%d\n",k);
	fclose(stdin);
	fclose(stdout);
	return 0;
}