Pagini recente » Cod sursa (job #1278755) | Cod sursa (job #1990335) | Cod sursa (job #404450) | Cod sursa (job #2682892) | Cod sursa (job #3224992)
#include <fstream>
#include <vector>
static size_t node_count;
static std::vector<std::vector<size_t>> adjacency;
static std::vector<bool> visited;
void dfs(size_t source) {
visited[source] = true;
for (size_t neighbor : adjacency[source]) {
if (!visited[neighbor])
dfs(neighbor);
}
}
int main() {
std::ifstream in("dfs.in");
std::ofstream out("dfs.out");
size_t line_count;
in >> node_count;
in >> line_count;
std::vector<size_t> empty_vector;
adjacency.insert(adjacency.begin(), node_count + 1, empty_vector);
visited.insert(visited.begin(), node_count + 1, false);
for (size_t index = 1; index <= line_count; index++) {
size_t source, destination;
in >> source >> destination;
adjacency[source].push_back(destination);
adjacency[destination].push_back(source);
}
size_t components = 0;
for (size_t source = 1; source <= node_count; source++) {
if (!visited[source]) {
dfs(source);
components++;
}
}
out << components << '\n';
return 0;
}