Cod sursa(job #715042)

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

struct Way {
	int a, b;
};

bool cmp(Way a, Way b) {
	return(a.a < b.a);
}

int n, m;
bool vis[100001];
int ind[100001];
Way way[400004];

void visit(int id) {
	vis[id] = 1;
	for (int i = ind[id]; way[i].a == id; ++i) {
		if (!vis[way[i].b]) {
			visit(way[i].b);
		}
	}
}

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

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

	int a, b;
	m = m * 2;
	for (int i = 0; i < m; ++i) {
		fscanf(in, "%d%d", &a, &b);
		way[i].a = a;
		way[i].b = b;
		++i;
		way[i].a = b;
		way[i].b = a;

	}
	std::sort(way, way + m, cmp);
	int k = 0;
	for (int i = 0; i < m; ++i) {
		if (k != way[i].a) {
			k = way[i].a;
			ind[k] = i;
		}
	}

	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);
}