Cod sursa(job #2388353)

Utilizator CoroloHorjea Cosmin Corolo Data 25 martie 2019 22:30:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

struct nod
{
      int val;
      nod *nnext;
};
struct nod *vecini[100005];
int v[100005], n, m;

struct nod *adauga(struct nod *h, int a)
{
      struct nod *p = (struct nod *)malloc(sizeof(nod));
      struct nod *cl;
      p->val = a;
      p->nnext = NULL;
      if (h == NULL)
      {
            h = p;
            return h;
      }
      else
      {
            cl = h;
            while (cl->nnext != NULL)
            {
                  cl = cl->nnext;
            }
            cl->nnext = p;
            return h;
      }
}

void dfs(int x)
{
      struct nod *cp;

      v[x] = 1;
      if (vecini[x] != NULL)
      {
            cp = vecini[x];
            while (cp != NULL)
            {
                  if (!v[cp->val])
                        dfs(cp->val);
                  cp = cp->nnext;
            }
      }
      // for (cp = vecini[x]; cp != NULL; cp = cp->nnext)
      //       if (!v[cp->val])
      //             dfs(cp->val);
}

int main()
{
      int a, b, componenete = 0;
      ;
      f >> n >> m;
      for (int i = 1; i <= n; i++)
      {
            vecini[i] = NULL;
            v[i] = 0;
      }
      for (int i = 1; i <= m; i++)
      {
            f >> a >> b;
            vecini[a] = adauga(vecini[a], b);
            vecini[b] = adauga(vecini[b], a);
      }
      f.close();
      for (int i = 1; i <= n; i++)
      {
            if (!v[i])
            {
                  dfs(i);
                  componenete++;
            }
      }
      g << componenete;
      g.close();
      return 0;
}