Pagini recente » Cod sursa (job #321872) | Cod sursa (job #1562860) | Cod sursa (job #670980) | Cod sursa (job #672880) | Cod sursa (job #3122129)
#include <bits/stdc++.h>
#define MAXN 100000
using namespace std;
using bitmap = bitset<MAXN>;
using graph = vector<vector<int>>;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
void dfs(graph& adj, int current, bitmap& checked) {
checked[current] = true;
for (auto& neighbour: adj[current])
if (!checked[neighbour])
dfs(adj, neighbour, checked);
}
int main() {
int n, m;
fin >> n >> m;
graph adj(n, vector<int>());
for (int i = 0; i < m; i++) {
int iNode, jNode;
fin >> iNode >> jNode;
iNode--, jNode--;
adj[iNode].push_back(jNode);
adj[jNode].push_back(iNode);
}
int count = 0;
bitmap checked;
for (int i = 0; i < n; i++) {
if (checked[i])
continue;
dfs(adj, i, checked);
count++;
}
fout << count;
return 0;
}