Cod sursa(job #1025131)

Utilizator macajouMaca George macajou Data 9 noiembrie 2013 15:37:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>

using namespace std;

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

nod *l[100010];
int n,m,k,viz[100010];

void adaug(nod *&pr, int x)
{
    nod *nou;
    nou=new nod;
    nou->vf=x;
    nou->urm=pr;
    pr=nou;
}

void citire()
{
    int i,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            adaug(l[x],y);
            adaug(l[y],x);
        }
}

void DFS(int vf)
{
    viz[vf]=k;
    nod *c;
    for(c=l[vf];c;c=c->urm)
        if(!viz[c->vf])
           DFS(c->vf);
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);

    int i;
    citire();
    for(i=1;i<=n;i++)
        if(!viz[i])
           {
               k++;
               DFS(i);
           }
    printf("%d",k);

    return 0;
}