Pagini recente » Cod sursa (job #2881624) | Cod sursa (job #1863200) | Cod sursa (job #1926246) | Cod sursa (job #1686386) | Cod sursa (job #2793785)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
class Graf
{
private:
static constexpr int NMAX = 100009;
const int N, M;
std::vector<int> Adiacenta[NMAX]; // liste de adiacenta
public:
Graf(int, int);
void AdMuchie(int, int);
void Bfs(int, int*);
int Dfs();
static constexpr int getNMAX() { return Graf::NMAX; }
private:
void Dfs_fHelper(int, bool*);
};
Graf::Graf(int n, int m)
: N(n), M(m)
{
}
void Graf::AdMuchie(int ini, int fin)
{
Adiacenta[ini].push_back(fin);
}
void Graf::Bfs(int S, int* nrArce)
{
int coada[NMAX], st = 0, dr = 0;
for (int i = 1; i <= N; ++i)
nrArce[i] = -1;
nrArce[S] = 0;
coada[st] = S;
while (st <= dr)
{
int curent = coada[st++];
for (auto it = Adiacenta[curent].begin(); it != Adiacenta[curent].end(); ++it)
if(nrArce[*it] == -1)
{
coada[++dr] = *it;
nrArce[*it] = nrArce[curent] + 1;
}
}
}
int Graf::Dfs()
{
bool vizitat[NMAX];
int nrComp = 0;
memset(vizitat, 0, NMAX * sizeof(bool));
for (int i = 1; i <= N; ++i)
if (!vizitat[i])
{
++nrComp;
Dfs_fHelper(i, vizitat);
}
return nrComp;
}
void Graf::Dfs_fHelper(int curent, bool* vizitat)
{
vizitat[curent] = true;
for (auto it = Adiacenta[curent].begin(); it != Adiacenta[curent].end(); ++it)
if (!vizitat[*it])
Dfs_fHelper(*it, vizitat);
}
int main()
{
std::ifstream f("dfs.in");
std::ofstream g("dfs.out");
int N, M;
f >> N >> M;
Graf graf(N, M);
for (int x, y, i = 0; i < M; ++i)
{
f >> x >> y;
graf.AdMuchie(x, y);
graf.AdMuchie(y, x);
}
g << graf.Dfs();
return 0;
}