Pagini recente » Cod sursa (job #1426500) | Clasamentul arhivei de probleme | Cod sursa (job #1923465) | Cod sursa (job #1221961) | Cod sursa (job #2195534)
#include <fstream>
#include <vector>
void dfs(int node, std::vector<bool> &visited, std::vector<int> *adj) {
visited[node] = true;
for (auto &neighbour : adj[node]) {
if (!visited[neighbour]) {
dfs(neighbour, visited, adj);
}
}
}
int main() {
std::ifstream in("dfs.in");
std::ofstream out("dfs.out");
int n, m;
in >> n >> m;
int nr = 0;
std::vector<int> adj[n + 1];
std::vector<bool> visited(n + 1, false);
int i;
int u, v;
for (i = 0; i < m; ++i) {
in >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (i = 1; i <= n; ++i) {
if (!visited[i]) {
++nr;
dfs(i, visited, adj);
}
}
out << nr;
in.close();
out.close();
return 0;
}