Cod sursa(job #1221758)

Utilizator pentrusandaPentru Sanda pentrusanda Data 21 august 2014 13:48:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>

using namespace std;

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

typedef nod *lda1;

lda1 lda[100005];

int n,m,x,y,parc[100005],nrcomp;

void parcurge(int nod)
{
    parc[nod]=1;
    for (lda1 p=lda[nod];p!=0;p=p->adr)
    {
        if (parc[p->urm]==0)
        {
            parcurge(p->urm);
        }
    }
}

int main()
{
    ifstream in ("dfs.in");
    ofstream out ("dfs.out");

    in>>n>>m;

    for (int i=1;i<=m;++i)
    {
        in>>x>>y;
        lda1 p=new nod;
        p->urm=y;
        p->adr=lda[x];
        lda[x]=p;
        p=new nod;
        p->urm=x;
        p->adr=lda[y];
        lda[y]=p;
    }

    for (int i=1;i<=n;++i)
    {
        if (parc[i]==0)
        {
            ++nrcomp;
            parcurge(i);
        }
    }

    out<<nrcomp;

    in.close();
    out.close();
    return 0;
}