Cod sursa(job #942992)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 23 aprilie 2013 22:55:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
using namespace std;

struct nod {
	int val;
	nod *adr;
};

nod *v[100005];
int n,m;
bool viz[100005];
int componente;

void insert(int a,int b) {
	if (v[a] == NULL) {
		nod *nou = new nod;
		nou->val = b;
		nou->adr = NULL;
		v[a] = nou;
	} else {
		nod *nou = new nod;
		nou->val = b;
		nou->adr = v[a];
		v[a] = nou;
	}
}

void fill(int a) {
	nod *crt;
	crt = v[a];
	viz[a] = true;
	while (crt != NULL) {
		if (!viz[crt->val]) fill(crt->val);
		crt = crt->adr;
	}
}

int main() {
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (int i=1;i<=n;i++) v[i] = NULL;
	for (int i=1;i<=m;i++) {
		int a,b;
		scanf("%d %d",&a,&b);
		insert(a,b);
		insert(b,a);
	}
	for (int i=1;i<=n;i++) if (!viz[i]) {
		componente++;
		fill(i);
	}
	printf("%d\n",componente);
	return 0;
}