Pagini recente » Cod sursa (job #1084374) | Cod sursa (job #2705502) | Cod sursa (job #2049211) | Cod sursa (job #2763047) | Cod sursa (job #2223874)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
typedef vector<vector<int>> Graph;
const string IN_FILE = "dfs.in";
const string OUT_FILE = "dfs.out";
void dfs(const Graph& graph, const int u, vector<bool>& visited) {
visited[u] = true;
for (const auto& v : graph[u]) {
if (!visited[v]) {
dfs(graph, v, visited);
}
}
}
int countComponents(const Graph& graph) {
int count = 0;
auto visited = vector<bool>(int(graph.size()));
for (int u = 0; u < int(graph.size()); u++) {
if (!visited[u]) {
count++;
dfs(graph, u, visited);
}
}
return count;
}
inline void addEdge(Graph& graph, const int u, const int v) {
graph[u].push_back(v);
graph[v].push_back(u);
}
Graph readGraph() {
ifstream in(IN_FILE);
int V, E;
in >> V >> E;
auto graph = Graph(V);
for (int i = 0; i < E; i++) {
int u, v;
in >> u >> v;
addEdge(graph, u - 1, v - 1);
}
return graph;
}
void writeOutput(const int components) {
ofstream out(OUT_FILE);
out << components << "\n";
out.close();
}
int main() {
const Graph& graph = readGraph();
const int components = countComponents(graph);
writeOutput(components);
return 0;
}