Cod sursa(job #943413)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 25 aprilie 2013 12:40:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <queue>
#include <bitset>

using namespace std;

struct element
{
    int indice;
    element *next;
};

struct nod
{
    element *cap;
    element *coada;
}v[100005];

void insert(int x,int y)
{
    element *p;
    if(v[x].cap==NULL)
    {
        v[x].cap=new element;
        v[x].coada=v[x].cap;
        v[x].cap->indice=y;
        v[x].cap->next=NULL;
    }
    else
    {
       p=new element;
       p->indice=y;
       p->next=NULL;
       v[x].coada->next=p;
       v[x].coada=p;
    }
}

queue<nod> cd;
bitset<100005> frec;

void dfs(int nod)
{
    cd.push(v[nod]);
    frec[nod]=1;

    element *p;


    while(!cd.empty())
    {
        for(p=cd.front().cap;p!=NULL;p=p->next)
        {
            if(!frec[p->indice])
            {
                frec[p->indice]=1;
                cd.push(v[p->indice]);
            }
        }
        cd.pop();
    }
}

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

    int n,m,i,x,y;
    fin>>n>>m;

    for(i=0;i<m;i++)
    {
        fin>>x>>y;
        insert(x-1,y-1);
        insert(y-1,x-1);
    }

    int cate=0;
    for(i=0;i<n;i++)
    {
        if(!frec[i])
        {
            cate++;
            dfs(i);
        }
    }

    fout<<cate<<'\n';
    fin.close();
    fout.close();
    return 0;
}