Cod sursa(job #233007)

Utilizator andyciupCiupan Andrei andyciup Data 16 decembrie 2008 18:37:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<stdio.h>
#define N 100005

int *a[N],n, contor=0;
bool viz[N];

void citesc_si_aloc()
{
	int m, x, y, d[N]={0};
	scanf("%d", &n);
	scanf("%d", &m);
	while(m--){
		scanf("%d%d", &x, &y);
		++d[x];
		++d[y];
	}
	fclose(stdin);
	freopen("dfs.in","r",stdin);
	for(int i=1; i<=n; ++i){
		a[i]=new int[1+d[i]];
		a[i][0]=0;
	}
}

void citesc2(){
	int m, x, y;
	scanf("%d", &n);
	scanf("%d", &m);
	while(m--){
		scanf("%d%d", &x, &y);
		a[x][++a[x][0]]=y;
		a[y][++a[y][0]]=x;
	}
}

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

void back(){
	for(int i=1; i<=n; ++i)
		if(viz[i]==false){
			dfs(i);
			contor++;
		}
	printf("%d\n", contor);
}


int main(){
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	citesc_si_aloc();
	citesc2();
	back();
	return 0;
}