Cod sursa(job #184253)

Utilizator stinkyStinky si Grasa stinky Data 23 aprilie 2008 12:44:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<stdio.h>

const int M=200010;
const int N=100010;

struct muchie{
	int x,y;
};

muchie e[M];

int *a[N], v[N], n, m;

bool viz[N];

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

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

int nrcomp(){
	int i,nr=0;
	for(i=1;i<=n;++i)
		if(!viz[i]){
			df(i);
			++nr;
		}
	return nr;
}

int main(){
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	citire();
	printf("%d\n",nrcomp());
	return 0;
}