Cod sursa(job #1580965)

Utilizator mihaimusatMihai Musat mihaimusat Data 26 ianuarie 2016 13:05:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#define NMAX  100005

using namespace std;

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

int n,m,i,x,y,nr,viz[NMAX];

struct nod{
int inf;
nod *urm;}*p,*v[NMAX];

void afis(nod *p)
{
    nod *u;
    u=p;
    while(u!=NULL)
    {
        g<<u->inf<<" ";
        u=u->urm;
    }
    g<<endl;
}

void adaug(nod *&p,int x)
{
    nod *u,*q;
    q=new nod;
    q->inf=x;
    q->urm=NULL;
    u=p;
    if(p==NULL) p=q;
    else
    {
        while(u->urm!=NULL)
        u=u->urm;
        u->urm=q;
    }
}

void BF(int X)
{
  int C[NMAX],p,u,k;
  nod *q;
  p=1;
  u=1;
  C[p]=X;
  viz[X]=1;
  while(p<=u)
  {
      k=C[p];
      q=v[k];
      while(q!=NULL)
      {
          if(viz[q->inf]==0)
          {
              C[++u]=q->inf;
              viz[q->inf]=1;
          }
          q=q->urm;
      }
      p++;
  }

}

int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
    v[i]=NULL;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        adaug(v[x],y);
        adaug(v[y],x);
    }
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            BF(i);
            nr++;
        }
    }
    g<<nr<<endl;

    return 0;
}