Pagini recente » Cod sursa (job #2927855) | Cod sursa (job #3194586) | Cod sursa (job #1096551) | Cod sursa (job #1412926) | Cod sursa (job #2689672)
#include <fstream>
#include <iostream>
#define NMAX 100001
struct Adiacenta
{
int nod;
Adiacenta *urm;
};
Adiacenta *Lista[NMAX];
int Viz[NMAX], NrComp;
int main()
{
std::ifstream f("dfs.in");
std::ofstream g("dfs.out");
int N, M, Stiv[NMAX], vf;
f >> N >> M;
for(int i = 1; i <= M; i++)
{
int a, b;
f >> a >> b;
Adiacenta *aux = new Adiacenta;
aux->nod = b;
aux->urm = Lista[a];
Lista[a] = aux;
aux = new Adiacenta;
aux->nod = a;
aux->urm = Lista[b];
Lista[b] = aux;
}
f.close();
int Nod_Verif = 1;
while(Nod_Verif <= N)
{
vf = 1;
Stiv[vf] = Nod_Verif;
Viz[Nod_Verif] = 1;
while(vf > 0)
{
int NodActual = Stiv[vf--];
Adiacenta *vecin = Lista[NodActual];
while(vecin != NULL)
{
if(!Viz[vecin->nod])
{
Stiv[++vf] = vecin->nod;
Viz[vecin->nod] = 1;
}
vecin = vecin->urm;
}
}
NrComp++;
Nod_Verif++;
while(Viz[Nod_Verif])
Nod_Verif++;
}
g << NrComp;
return 0;
}