Cod sursa(job #974777)

Utilizator gabriel93Robu Gabriel gabriel93 Data 18 iulie 2013 12:31:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <stdio.h>
#define Nmax 100002
using namespace std;
int n,m,c;
int viz[Nmax];

struct graf
{
    int v;
    graf *adr;
};
graf *g[Nmax];

void add(int v1,int v2)
{
    graf *p;
    p=new graf;
    p->v=v2;
    p->adr=g[v1];
    g[v1]=p;
}

void citire()
{
    int i,v1,v2;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d %d",&v1,&v2);
        add(v1,v2);
        add(v2,v1);
    }
}

void dfs()
{
    int i,st[Nmax],s,ok;
    graf *p;
    for(i=1;i<=n;++i)
        if(viz[i]==0)
        {
            ++c;
            st[1]=i;
            s=1;
            viz[i]=1;
            while(s>0)
            {
                ok=0;
                for(p=g[st[s]];p;p=p->adr)
                    if(viz[p->v]==0)
                    {
                        ++s;
                        st[s]=p->v;
                        viz[p->v]=1;
                        ok=1;
                        break;
                    }
                if(ok==0)
                    --s;
            }
        }
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    citire();
    dfs();
    printf("%d\n",c);
    fclose(stdin);
    fclose(stdout);
    return 0;
}