Cod sursa(job #2681743)

Utilizator corina_dimitriuDimitriu Corina corina_dimitriu Data 6 decembrie 2020 15:57:25
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#define DMAX 105

using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

int A[DMAX][DMAX],viz[DMAX];

struct nod {int info; nod *urm;};
struct stiva{nod *prim;};

void insereaza(stiva &S, int x)
{
    nod* nod_nou;
    nod_nou=new nod;
    nod_nou->info=x;
    nod_nou->urm=S.prim;
    S.prim=nod_nou;
}

int citeste(stiva S)
{
    return S.prim->info;
}

void elimina(stiva &S)
{
    nod *q;
    q=S.prim;
    S.prim=S.prim->urm;
    delete(q);
}

void DFS(int nod, int n)
{
    stiva S;
    int i,j;
    S.prim=NULL;
    insereaza(S,nod);
    while(S.prim!=NULL)
    {
        j=citeste(S);
        elimina(S);
        //fout<<j<<' ';
        for(i=1;i<=n;i++)
           if(A[j][i]==1&&viz[i]==0)
              {
               viz[i]=1;
               insereaza(S,i);
              }
    }
}

int main()
{
    int n,m,X,i,a,b,sol=0;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b;
        A[a][b]=A[b][a]=1;
    }
    for(X=1;X<=n;X++)
        if(viz[X]==0)
       {
           viz[X]=1;
           DFS(X,n);
           sol++;
       }
    fout<<sol<<'\n';
    return 0;
}