Pagini recente » Cod sursa (job #645518) | Cod sursa (job #1500028) | Cod sursa (job #1626944) | Cod sursa (job #1192448) | Cod sursa (job #2807850)
#include <iostream>
#include <list>
#include <vector>
#include <fstream>
using namespace std;
const int nMax = 100005;
//int n, m, nrComp;
class Graf {
private:
int m_n, m_m;
list<int> listAd[nMax];
// DFS
bool dfsViz[nMax] = {};
public:
explicit Graf(int n = 0, int m = 0) : m_n(n), m_m(m) {}
void neorientatCitesteListaAdiacenta(ifstream &in) {
for (int i = 0; i < m_m; i++) {
int x, y;
in >> x >> y;
listAd[x].push_back(y);
listAd[y].push_back(x);
}
}
void neorientatDFS(int k) {
dfsViz[k] = true;
for (auto x: listAd[k]) {
if (!dfsViz[x]) {
neorientatDFS(x);
}
}
}
int neorientatNrCompConexe() {
int nrComp = 0;
for (int i = 1; i <= m_n; i++) {
if (!dfsViz[i]) {
nrComp++;
neorientatDFS(i);
}
}
return nrComp;
}
};
int main() {
// Input rapid
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// Input
ifstream in("dfs.in");
ofstream out("dfs.out");
int n, m;
in >> n >> m;
Graf g(n, m);
g.neorientatCitesteListaAdiacenta(in);
out << g.neorientatNrCompConexe();
in.close();
out.close();
return 0;
}