Cod sursa(job #715041)

Utilizator DSzprogDombi Szabolcs DSzprog Data 16 martie 2012 15:35:23
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 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[200002];

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);
	for (int i = 0; i < m; ++i) {
		fscanf(in, "%d%d", &way[i].a, &way[i].b);
	}
	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);
}