Cod sursa(job #2168257)

Utilizator PristandaAmaliaPristanda Amalia PristandaAmalia Data 14 martie 2018 10:11:30
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#define NMAX 100002
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, nr;

void desc(int);
void citire();
void dfs(int start);
void inserare(LSI& L, int x, nod* p);

int main()
{int i;
 citire();
 for (i=1; i<=n; i++)
      if(!uz[i])
         {++nr;
          dfs(i);
         }
 fout<<nr;
 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;
        }
}

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;
    }
}