Cod sursa(job #2633775)

Utilizator emcerchezEmanuela Cerchez emcerchez Data 8 iulie 2020 15:36:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
using namespace std;
#define NMAX 100001
ifstream fin("dfs.in");
ofstream fout("dfs.out");

struct Nod
      {int vf;
       struct Nod * urm;
      };
typedef struct Nod * Lista;

int n;
Lista A[NMAX];
int uz[NMAX];
int nrc;

void citire();
void dfs(int x);

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

void citire()
{int i, x, y, m;
 Lista p;
 fin>>n>>m;
 for (i=0; i<m; i++)
     {
      fin>>x>>y;
      //inseram pe x in lista lui y
      p=new Nod;  p->vf=x; p->urm=A[y]; A[y]=p;
      //inseram pe y in lista lui x
      p=new Nod;  p->vf=y; p->urm=A[x]; A[x]=p;
     }
}

void dfs(int x)
{Lista p;
 uz[x]=1;
 for (p=A[x]; p; p=p->urm)
      if (!uz[p->vf])
          dfs(p->vf);
}