Pagini recente » Cod sursa (job #17994) | Cod sursa (job #1998075) | Cod sursa (job #1026053) | Cod sursa (job #2419646) | Cod sursa (job #948150)
Cod sursa(job #948150)
#include <fstream>
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <vector>
using namespace std;
template <class T>
class graph {
public:
graph() {}
template <class ForwardIterator>
graph(ForwardIterator begin, ForwardIterator end)
: nodes(begin, end) {}
void add_edge(T src, T dst) {
nodes.insert(src);
nodes.insert(dst);
edges[src].push_back(dst);
edges[dst].push_back(src);
}
int connected_components() {
int result = 0;
unordered_set<T> visited;
for (T node : nodes) {
if (visited.count(node) == 0) {
++result;
dfs(node, visited);
}
}
return result;
}
private:
void dfs(T node, unordered_set<T>& visited) {
visited.insert(node);
for (T next : edges[node]) {
if (visited.count(next) == 0)
dfs(next, visited);
}
}
unordered_set<T> nodes;
unordered_map<T, vector<T>> edges;
};
int main()
{
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int N, M;
fin >> N >> M;
vector<int> v(N);
for (int i = 1; i <= N; ++i)
v[i - 1] = i;
graph<int> g(begin(v), end(v));
for (int i = 0; i < M; ++i) {
int x, y;
fin >> x >> y;
g.add_edge(x, y);
}
fout << g.connected_components() << "\n";
return 0;
}