Pagini recente » Cod sursa (job #2008369) | Cod sursa (job #1035949) | Cod sursa (job #213466) | Cod sursa (job #1520257) | Cod sursa (job #2922262)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
void DFS (vector<vector<int>> &graph, int node, unordered_set<int> &seen) {
seen.insert(node);
for (auto neighbour : graph[node]) {
if (seen.find(neighbour) == seen.end())
seen.insert(neighbour), DFS(graph, neighbour, seen);
}
}
void count (vector<vector<int>> &graph) {
unordered_set<int> comp;
int ans = 0, n = graph.size() - 1;
for (int i = 1; i <= n; ++i) {
if (comp.find(i) == comp.end()) {
++ans;
DFS(graph, i, comp);
}
}
fout << ans;
}
int main()
{
vector<vector<int>> nodes;
int n, m;
fin >> n >> m;
nodes.resize(n + 1);
while (m) {
int x, y;
fin >> x >> y;
nodes[x].push_back(y);
nodes[y].push_back(x);
--m;
}
count(nodes);
return 0;
}