Cod sursa(job #2168181)

Utilizator alexandra.ioana.popaPopa Alexandra-Ioana alexandra.ioana.popa Data 14 martie 2018 09:54:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#define NMAX 100005
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

struct nod
{
    int vf;
    struct nod* urm;
};

typedef struct nod*  LSI;
LSI L[NMAX]; //aici vom avea pe L[i] vecinii vectorului i; L[i] va indica inceputul listei de adiacenta;
nod* p[NMAX]; //acestia vor indica ultimul nod pus, initial indica null;
bool uz[NMAX];

int n, m;

void initializare();
void citire();
void dfs(int start);

void inserare(LSI& L, int x, nod* p);

int main()
{int i, contor=0;
    citire();
    for (i=1; i<=n; i++)
        if (uz[i]==0)
            {
            dfs(i);
            contor++;
            }
    fout<<contor<<'\n';
    return 0;
}

void dfs(int x)
{
 nod* p;
 uz[x]=1; //marchez varful in care sunt;
 for (p=L[x]; p!=NULL; p=p->urm)
    if (uz[p->vf]==0)
        dfs(p->vf);
}

void citire()
{int x, y, i;
    fin>>n>>m;
    for (i=1; i<=m; i++)
        {
         fin>>x>>y;
         inserare(L[x], y, p[x]);
         if (p[x]==NULL)
            p[x]=L[x];
            else
            p[x]=p[x]->urm; //adica ne ducem tot la ultimul nod adaugat;

         inserare(L[y], x, p[y]);
         if (p[y]==NULL)
            p[y]=L[y];
            else
            p[y]=p[y]->urm; //adica ne ducem tot la ultimul nod adaugat;
        }
}

void inserare(LSI& L, int x, nod* p)
{
    nod* q = new nod;
    q->vf=x;
    if (p==NULL) //daca introducem la inceputul listei
        {
        q->urm=L;
        L=q;
        }
        else
        {
        q->urm = p->urm;
        p->urm = q;
        }
}