Pagini recente » Cod sursa (job #2621811) | Cod sursa (job #886385) | Cod sursa (job #1469794) | Cod sursa (job #412257) | Cod sursa (job #2348120)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
void dfs(
int nod, vector<bool>& vizitate,
const vector<vector<int>>& adiacenta
) {
vizitate[nod] = true;
for (int vecin = 0; vecin < adiacenta[nod].size(); ++vecin) {
int ivecin = adiacenta[nod][vecin];
if (!vizitate[ivecin]) {
dfs(ivecin, vizitate, adiacenta);
}
}
}
int main() {
ifstream in("dfs.in");
vector<vector<int>> muchii;
int n;
in >> n;
muchii.resize(n + 1);
int m;
in >> m;
for (int i = 0; i < m; ++i) {
int start, end;
in >> start >> end;
muchii[start].push_back(end);
muchii[end].push_back(start);
}
in.close();
vector<bool> vizitate;
vizitate.resize(n);
int comp = 0;
for (int i = 0; i < n; ++i) {
if (!vizitate[i]) {
dfs(i, vizitate, muchii);
++comp;
}
}
ofstream out("dfs.out");
out << comp << '\n';
}