Cod sursa(job #1167407)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 4 aprilie 2014 22:16:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 100005;
int n, m;
vector<int> g[MAXN];

const int buff_size = 1 << 17;
char buff[buff_size];

inline bool digit(const char &a) {
	if ('0' <= a && a <= '9')
		return true;
	return false;
}

inline void nextInt(int &a) { a = 0;
	static int i = buff_size;
	if (i == buff_size)
		fread(buff, 1, buff_size, stdin), i = 0;
	while (!digit(buff[i]))
		if (++i == buff_size)
			fread(buff, 1, buff_size, stdin), i = 0;
	while (digit(buff[i])) {
		a = a * 10 + buff[i] - '0';
		if (++i == buff_size)
			fread(buff, 1, buff_size, stdin), i = 0;
	}
}

bool ap[MAXN];

inline void dfs(const int &node) {
	ap[node] = true;
	for (size_t j = 0; j < g[node].size(); ++j) {
		int next = g[node][j];
		if (!ap[next])
			dfs(next);
	}
}

int main() {
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	
	nextInt(n); nextInt(m);
	for (int i = 1; i <= m; ++i) {
		int x, y;
		nextInt(x); nextInt(y);
		g[x].push_back(y); g[y].push_back(x);
	}
	
	int res = 0;
	for (int i = 1; i <= n; ++i)
		if (!ap[i])
			dfs(i), ++res;
	
	printf("%d\n", res);
}