Cod sursa(job #882034)

Utilizator VladMSBonta vlad valentin VladMS Data 18 februarie 2013 20:40:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct nod
{
    int info;
    nod *next;
};
nod *p,*l[100001];
int x,y,i,j,n,viz[100001],cs,cd,co[100001],ok,a,b,k,poz,m,rez;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y;
        if(x!=y)
        {
        p=new nod;
        p->next=l[x];
        p->info=y;
        l[x]=p;
        p=new nod;
        p->next=l[y];
        p->info=x;
        l[y]=p;
        }
    }
    while(b<=n)
    {
    ok=1;
    cs=1;
    cd=1;
    b++;
    a=b;
    if(viz[b]==0&&b<=n)
    {
    viz[a]=a;
    co[cd]=a;
    ok=1;
    rez++;
        while(cs<=cd)
        {
            p=new nod;
            p=l[a];
            while(p)
                {
                    if(viz[p->info]==0)
                        {co[++cd]=p->info;
                        viz[p->info]=b;
                        }

                    p=p->next;
                }

            a=co[++cs];
        }


    }
    }

fout<<rez;
    return 0;
}