Cod sursa(job #662033)

Utilizator Laura_MMiclescu Laura Laura_M Data 15 ianuarie 2012 18:36:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 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)
           {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=1; i<=M; i++)
          {f>>X>>Y;
           adaugare(X,Y);
           adaugare(Y,X);}
      for (i=1; i<=N; i++)
           if (viz[i]==0)
              {DFS(i);
               componente++;}
      g<<componente;
      return 0;
}