Cod sursa(job #2689672)

Utilizator XeinIonel-Alexandru Culea Xein Data 21 decembrie 2020 20:07:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#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;
}