Pagini recente » Cod sursa (job #2597369) | Cod sursa (job #2697151) | Cod sursa (job #1932524) | Cod sursa (job #2657646)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define MAX_N 100000
#define MAX_M 200000
int vizite[MAX_N+1];
vector<int> listaVecini[MAX_M];
void parcurgereDFS(int nodStart) {
vizite[nodStart] = 1;
for (int i = 0; i < listaVecini[nodStart].size(); i++) {
int vecin = listaVecini[nodStart][i];
if (vizite[vecin] == 0)
parcurgereDFS(vecin);
}
}
int gasireNumarConexe(int nrNoduri) {
int componenteConexe = 0;
for (int i = 1; i <= nrNoduri; i++)
if (vizite[i] == 0){
parcurgereDFS(i);
componenteConexe++;
}
return componenteConexe;
}
ifstream f("dfs.in");
ofstream g("dfs.out");
int main() {
int n,m;
f>>n>>m;
for (int i = 0; i < m; i++) {
int sursa, destinatie;
f>>sursa>>destinatie;
listaVecini[sursa].emplace_back(destinatie);
// E graf NEORIENTAT
listaVecini[destinatie].emplace_back(sursa);
}
g<<gasireNumarConexe(n);
f.close();
g.close();
return 0;
}