Pagini recente » Cod sursa (job #2944660) | Cod sursa (job #2883719) | Cod sursa (job #2476394) | Cod sursa (job #26351) | Cod sursa (job #1597501)
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
using namespace std;
template <class T>
class graph {
unordered_map<T, vector<T>> neighbors;
unordered_set<T> nodes;
void depth_first_search(T node, unordered_set<T>& visited) {
visited.insert(node);
for (auto next : neighbors[node]) {
if (visited.find(next) == visited.end()) {
depth_first_search(next, visited);
}
}
}
public:
template <class Iterator>
graph(Iterator begin, Iterator end):
nodes(begin, end) {}
void add_edge(T src, T dst) {
neighbors[src].push_back(dst);
}
unordered_map<T, int> breadth_first_search(T node) {
unordered_map<T, int> result;
unordered_set<T> visited;
queue<T> q;
result[node] = 0;
q.push(node);
visited.insert(node);
while (!q.empty()) {
auto x = q.front(); q.pop();
for (auto next : neighbors[x]) {
if (visited.find(next) == visited.end()) {
visited.insert(next);
result[next] = result[x] + 1;
q.push(next);
}
}
}
for (auto other : nodes) {
if (other != node && result[other] == 0)
result[other] = -1;
}
return result;
}
int connected_components() {
unordered_set<T> visited;
int result = 0;
for (auto node : nodes) {
if (visited.find(node) == visited.end()) {
result += 1;
depth_first_search(node, visited);
}
}
return result;
}
};
int main() {
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n, m;
fin >> n >> m;
vector<int> nodes;
for (int i = 1; i <= n; ++i) {
nodes.push_back(i);
}
graph<int> G(nodes.begin(), nodes.end());
for (int i = 0; i < m; ++i) {
int src, dst;
fin >> src >> dst;
G.add_edge(src, dst);
G.add_edge(dst, src);
}
fout << G.connected_components() << endl;
return 0;
}