Pagini recente » Cod sursa (job #387760) | Cod sursa (job #1968784) | Cod sursa (job #2837254) | Cod sursa (job #591871) | Cod sursa (job #2868314)
#include <array>
#include <cstdint>
#include <fstream>
#include <vector>
using i32 = int32_t;
using u32 = uint32_t;
constexpr size_t MAX_NODES = 100000;
std::array<std::vector<size_t>, MAX_NODES> edges;
size_t nodeCount;
std::array<bool, MAX_NODES> viz;
void dfs (size_t node) {
viz[node] = true;
for (auto to: edges[node])
if (!viz[to])
dfs(to);
}
int main () {
std::ifstream in("dfs.in");
std::ofstream out("dfs.out");
size_t edgeCount;
in >> nodeCount >> edgeCount;
for (size_t i = 0; i != edgeCount; ++ i) {
size_t x, y;
in >> x >> y;
-- x, -- y;
edges[x].emplace_back(y);
edges[y].emplace_back(x);
}
size_t strongComponentCount = 0;
for (size_t node = 0; node != nodeCount; ++ node)
if (!viz[node]) {
++ strongComponentCount;
dfs(node);
}
out << strongComponentCount;
}