Pagini recente » Cod sursa (job #1780659) | Cod sursa (job #2252843) | Cod sursa (job #2767153) | Cod sursa (job #800085) | Cod sursa (job #2767162)
#include <iostream>
#include <fstream>
#include <list>
std::list<int> adj[100005];
int visited[100005];
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
// dfs algorithm
void dfs(int source) {
visited[source] = 1;
for (auto it = adj[source].begin(); it != adj[source].end(); it++) {
if (!visited[*it]) {
dfs(*it);
}
}
}
int main(void) {
int n, m, nr_comp = 0;
// read inputs
fin >> n >> m;
for (int i = 0; i < m; ++i) {
int n1, n2;
fin >> n1 >> n2;
adj[n1].push_back(n2);
adj[n2].push_back(n1);
}
for (int i = 1; i <= n; ++i) {
if (visited[i] == 0) {
nr_comp++;
dfs(i);
}
}
fout << nr_comp;
fin.close();
fout.close();
return 0;
}