Pagini recente » Cod sursa (job #2676245) | Cod sursa (job #881201) | Cod sursa (job #1111223) | Cod sursa (job #43172) | Cod sursa (job #2787577)
#include <fstream>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
class GrafNeorientat
{
private:
int nrNoduri;
int nrMuchii;
vector <bool> vizitat;
map <int, vector<int>> adiacenta;
public:
GrafNeorientat();
void DFS(int start);
void NumaraCompCnx();
};
GrafNeorientat::GrafNeorientat()
{
ifstream in("dfs.in");
in >> this->nrNoduri;
in >> this->nrMuchii;
for (int i = 0; i < nrNoduri; ++i)
vizitat.push_back(false);
int start;
int capat;
for (int i = 0; i < nrMuchii; ++i)
{
in >> start >> capat;
adiacenta[start].push_back(capat);
adiacenta[capat].push_back(start);
}
in.close();
}
void GrafNeorientat::DFS(int start)
{
vizitat[start] = true;
for (int nod : adiacenta[start])
{
if (!vizitat[nod])
DFS(nod);
}
}
void GrafNeorientat::NumaraCompCnx()
{
ofstream out("dfs.out");
int nrCompCnx = 0;
for(int i = 0; i < nrNoduri; ++i)
if (!vizitat[i])
{
DFS(i);
nrCompCnx++;
}
out << nrCompCnx;
}
int main()
{
GrafNeorientat g;
g.NumaraCompCnx();
return 0;
}