Pagini recente » Cod sursa (job #556300) | Cod sursa (job #1590541) | Cod sursa (job #770685) | Cod sursa (job #627196) | Cod sursa (job #2348128)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
using ListaVecini = vector<int>;
using ListaAdiacenta = vector<ListaVecini>;
void dfs(
int nod, vector<bool>& vizitate,
const ListaAdiacenta& adiacenta
) {
vizitate[nod] = true;
for (int i = 0; i < adiacenta[nod].size(); ++i) {
int vecin = adiacenta[nod][i];
if (!vizitate[vecin]) {
dfs(vecin, vizitate, adiacenta);
}
}
}
int main() {
ifstream in("dfs.in");
ListaAdiacenta 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 = 1; i <= n; ++i) {
if (!vizitate[i]) {
dfs(i, vizitate, muchii);
++comp;
}
}
ofstream out("dfs.out");
out << comp << '\n';
}