Cod sursa(job #715043)

Utilizator DSzprogDombi Szabolcs DSzprog Data 16 martie 2012 15:42:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>

struct Conn {
	int node;
	Conn * next;
};

int n, m;
bool vis[100001];
Conn * ind[100001];

void add(int a, int b) {
	Conn * conn = new Conn();
	conn->node = b;
	conn->next = ind[a];
	ind[a] = conn;
}

void visit(int id) {
	vis[id] = 1;
	Conn * next = ind[id];
	while (next) {
		if (!vis[next->node]) {
			visit(next->node);
		}
		next = next->next;
	}
}

int main() {
	FILE * in = fopen("dfs.in", "rt");
	FILE * out = fopen("dfs.out", "wt");

	fscanf(in, "%d%d", &n, &m);

	int a, b;
	for (int i = 0; i < m; ++i) {
		fscanf(in, "%d%d", &a, &b);
		add(a, b);
		add(b, a);
	}

	int count = 0;
	for (int i = 1; i <= n; ++i) {
		if (!vis[i]) {
			visit(i);
			++count;
		}
	}

	fprintf(out, "%d\n", count);

	fclose(in);
	fclose(out);
}