Pagini recente » Cod sursa (job #712348) | Cod sursa (job #1726091) | Cod sursa (job #49820) | Cod sursa (job #520747) | Cod sursa (job #2787614)
#include <fstream>
#include <vector>
#include <map>
using namespace std;
const int noduriMAX = 100001;
class GrafNeorientat
{
private:
int nrNoduri;
int nrMuchii;
bool vizitat[noduriMAX];
vector <vector<int>> adiacenta;
public:
GrafNeorientat();
void DFS(int start);
void NumaraCompCnx();
};
GrafNeorientat::GrafNeorientat()
{
ifstream in("dfs.in");
in >> nrNoduri;
in >> nrMuchii;
for (int i = 1; i <= nrNoduri; ++i)
vizitat[i] = false;
int start;
int capat;
adiacenta.resize(nrNoduri + 1);
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 vecin : adiacenta[start])
{
if (!vizitat[vecin])
DFS(vecin);
}
}
void GrafNeorientat::NumaraCompCnx()
{
ofstream out("dfs.out");
int nrCompCnx = 0;
for (int i = 1; i <= nrNoduri; ++i)
{
if (!vizitat[i])
{
DFS(i);
nrCompCnx++;
}
}
out << nrCompCnx;
out.close();
}
int main()
{
GrafNeorientat g;
g.NumaraCompCnx();
return 0;
}