Pagini recente » Cod sursa (job #1017546) | Cod sursa (job #2268824) | Cod sursa (job #1112867) | Cod sursa (job #1636446) | Cod sursa (job #2793349)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int nmax = 100010;
class Graf
{
private:
bool orientat;
int nrNoduri;
vector <int> listaAdiacenta[nmax];
public:
Graf(int nrNoduri = 0, bool orientat = false);
int get_nrNoduri();
void citireMuchii(int nrMuchii);
vector<int> BFS(int start);
void DFS(int nodCurent, bool *vizitatDFS);
int nrComponenteConexe();
};
Graf :: Graf(int nrNoduri, bool orientat) : nrNoduri(nrNoduri), orientat(orientat)
{
this->orientat = orientat;
this->nrNoduri = nrNoduri;
}
int Graf::get_nrNoduri()
{
return this->nrNoduri;
}
void Graf::citireMuchii(int nrMuchii)
{
int nod1, nod2;
for(int i = 0; i < nrMuchii; i++)
{
in >> nod1 >> nod2;
listaAdiacenta[nod1].push_back(nod2);
if(!orientat)
{
listaAdiacenta[nod2].push_back(nod1);
}
}
}
void Graf::DFS(int nodCurent, bool *vizitatDFS)
{
vizitatDFS[nodCurent] = true;
for(auto vecin:listaAdiacenta[nodCurent])
{
if(!vizitatDFS[vecin])
{
DFS(vecin, vizitatDFS);
}
}
}
int Graf::nrComponenteConexe()
{
int contorComponente = 0;
bool vizitat[nmax]={false};
for(int i = 1; i <= nrNoduri; i++)
{
if(!vizitat[i])
{
DFS(i, vizitat);
contorComponente++;
}
}
return contorComponente;
}
int main() {
int n, m;
in >> n >> m;
Graf g(n,false);
g.citireMuchii(m);
out << g.nrComponenteConexe();
return 0;
}