Cod sursa(job #2168285)

Utilizator sabina.hutanuSabina Hutanu sabina.hutanu Data 14 martie 2018 10:17:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#define NMAX 100002

using namespace std;

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

struct nod
{
    int vf;
    struct nod* urm;
};

typedef struct nod*  LSI;
LSI L[NMAX];
bool viz[NMAX], viz2[NMAX];

int n, m, start, i, comp, nr;

void citire();
void dfs(int);
void bfs(int);
void ins(LSI& L, int x);




int main()
{
    citire();
    for (i=1; i<=n; i++)
        if(!viz[i])
        {
            nr++;
            dfs(i);
        }
    fout<<nr<<'\n';
    /*bfs(start);
    for(i=1; i<=n; i++)
        if(nrpasi[i]==0 && i!=start)
            fout<<-1<<' ';
        else
            fout<<nrpasi[i]<<' ';*/
    return 0;
}

void dfs(int x)
{
    nod* p;
    viz[x]=1;
    for (p=L[x]; p!=NULL; p=p->urm)
        if (viz[p->vf]==0)
            dfs(p->vf);
}

void citire()
{int i, x, y;
    fin>>n>>m;
    for(i=1; i<=m; i++)
        {
            fin>>x>>y;
            ins(L[x], y);
            ins(L[y], x);
        }
}

/*void bfs(int start)
{
    int C[NMAX], x, prim, ultim;
    nod* q;
    C[0]=start;
    prim=ultim=0;
    viz2[start]=1;
    while(prim<=ultim)
    {
        x=C[prim++];
        for(q=L[x]; q; q=q->urm)
            if(!viz2[q->vf])
                {
                    viz2[q->vf]=1;
                    C[++ultim]=q->vf;
                    nrpasi[q->vf]=nrpasi[x]+1;
                }
    }
}*/

void ins(LSI& L, int x)
{
    LSI p=new nod;
    p->vf=x;
    p->urm=L;
    L=p;
}