Pagini recente » Cod sursa (job #908509) | Cod sursa (job #926778) | Cod sursa (job #2849623) | Cod sursa (job #821505) | Cod sursa (job #2606351)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <limits>
class Graph {
public:
Graph(const std::string &filename) {
std::ifstream fin(filename);
int n, m;
fin >> n >> m;
adj_list.resize(n + 1, std::vector<int>());
int f, g, h;
for (int i = 0; i < m; i++) {
fin >> f >> g;
adj_list[f].push_back(g);
adj_list[g].push_back(f);
}
fin.close();
}
int num_conn_comp() {
std::vector<bool> seen(adj_list.size());
int k = 0;
for (int i = 1; i < adj_list.size(); i++) {
if (seen[i] == 0) {
k++;
dfs(i, seen);
}
}
return k;
}
private:
void dfs(int i, std::vector<bool> &seen) {
if (seen[i] == 1) return;
seen[i] = 1;
for (int e:adj_list[i])
dfs(e, seen);
}
private:
std::vector<std::vector<int>> adj_list;
};
int main() {
Graph graph("dfs.in");
std::ofstream fout("dfs.out");
fout << graph.num_conn_comp();
fout.close();
}