Cod sursa(job #409729)

Utilizator dead_knightTitei Paul Adrian dead_knight Data 3 martie 2010 20:29:00
Problema Radiatie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include<cstdio>
#include<fstream>
using namespace std;
struct nod{
int info;
nod *next;
};
nod *a[100005];
int n,m,nrc=0,v[100005];

void citire()
{
    freopen("dfs.in","r",stdin);
    scanf("%d%d", &n, &m);
    int i,x,y;
    nod  *p;
    for(i=1;i<=n;i++)
        a[i]=NULL;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d", &x, &y);
        p=new nod;
        p->info=y;
        p->next=a[x];
        a[x]=p;
        p=new nod;
        p->info=x;
        p->next=a[y];
        a[y]=p;
    }
}

void write()
{
    int i;
    for(i=1;i<=n;i++)
    {
        printf("%d: ",i);
        for(nod *p=a[i];p;p=p->next)
            printf("%d ", p->info);
        printf("\n");
    }
}

void dfs(int varf, int nrc)
{
    v[varf]=nrc;
    for(nod *p=a[varf];p;p=p->next)
        if(v[p->info]==0)
            dfs(p->info,nrc);
}

void bfs(int varf, int nrc)
{
    int k;
    nod *st,*dr;
    st=dr=new nod;
    st->info=varf;
    st->next=NULL;
    dr=st;
    v[varf]=nrc;
    while(st)
    {
        k=st->info;
        for(nod *p=a[k];p;p=p->next)
        {
            if(v[p->info]==0)
            {
                v[p->info]=nrc;
                nod *q=new nod;
                q->info=p->info;
                q->next=NULL;
                dr->next=q;
                dr=q;
            }
        }
        nod *t=new nod;
        t=st;
        st=st->next;
        delete t;
    }
}


int main()
{
    int i;
    citire();
    for(i=1;i<=n;i++)
        if(v[i]==0)
            bfs(i,++nrc);
    freopen("dfs.out","w",stdout);
    //write();
    printf("%d",nrc);
    return 0;
}