Cod sursa(job #662023)

Utilizator Laura_MMiclescu Laura Laura_M Data 15 ianuarie 2012 18:24:04
Problema Parcurgere DFS - componente conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>

#define MAXIM 100005

using namespace std;

struct nod
     {int inf;
      nod *urm;}*a[MAXIM];
      
int N, M, viz[MAXIM];

void adaugare (int i, int t)
{
     nod *q;
     q=new nod;
     q->inf=t;
     q->urm=a[i];
     a[i]=q;
}

void DFS(int k)
{
     nod *q;
     q=a[k];
     viz[k]=1;
     while (q!=NULL)
           {if (viz[q->inf]==0)
                DFS(q->inf);
                q=q->urm;}
}

int main()
{
      int i, X, Y, componente=0;
      ifstream f("dfs.in");
      ofstream g("dfs.out");
      f>>N>>M;
      for (i=0; i<M; ++i)
          {f>>X>>Y;
           adaugare(X,Y);
           adaugare(Y,X);}
      for (i=0; i<N; ++i)
           if (viz[i]==0)
              {DFS(i);
               componente++;}
      g<<componente;
      return 0;
}