Pagini recente » Cod sursa (job #935388) | Cod sursa (job #249074) | Cod sursa (job #2465507) | Cod sursa (job #2972077) | Cod sursa (job #2782438)
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
class Graf {
public:
void DFS(int nod, vector<bool> &viz) {
viz[nod] = true;
for (auto &x : m_ad[nod]) {
if (!viz[x]) {
DFS(x, viz);
}
}
}
int CompConexe() {
int nrComp = 0;
vector<bool> viz(m_n, false);
for (int i = 1; i <= m_n; ++i) {
if (!viz[i]) {
++nrComp;
DFS(i, viz);
}
}
return nrComp;
}
Graf(int n, vector<vector<int>> &ad) : m_n(n), m_ad(ad) {}
private:
int m_n;
vector<vector<int>> m_ad;
};
int main() {
int n, m, x, y;
fin >> n >> m;
vector<vector<int>> ad(n + 1);
for (int i = 1; i <= m; ++i) {
fin >> x >> y;
ad[x].push_back(y);
ad[y].push_back(x);
}
Graf G(n, ad);
fout << G.CompConexe();
return 0;
}