Cod sursa(job #1244808)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 18 octombrie 2014 11:22:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.33 kb
#include <cstdio>

using namespace std;

class element{
public:
    element(){ /// constructor care atribuie valoarea 0
        this->inf = 0;
    }
    element(int x){
        this->inf = x;
    }
    int inf;
};

class nod{
public:
    nod(){
        e.inf = 0;
        next = prev = 0;
    }
    nod(element el, nod *p, nod *n){ /// constructor care imi da
        this->next = n;              /// relatia dintre vecini si element curent
        this->prev = p;
        this-> e = el;
    }
    element e;
    nod *next,*prev;
};

class lista{
public:
    lista(){
        Begin = End = 0;
    }
    nod *Begin,*End;
    bool Empty(){
        if(End == 0)
            return 1;
        return 0;
    }
    void Push_back(element e){
        if(Empty()){
            nod *aux = new nod(e,0,0);
            Begin = End = aux;
            return;
        }
        nod *aux = new nod(e,End,0);
        End->next = aux;
        End = End->next;
    }
    void Push_front(element e){
        if(Empty()){
            nod *aux = new nod(e,0,0);
            Begin = End = aux;
            return;
        }
        nod * aux = new nod(e,0,Begin);
        Begin->prev = aux;
        Begin = Begin->prev;
    }
    void Pop_front(){
        nod *aux = Begin;
        Begin = Begin->next;
        if(Begin)
            Begin->prev = 0;
        else
            End = 0;
        delete aux;
    }
};

lista Graf[100005]; /// Graf[i] -> lista de vecini a nodului i
int viz[100005]; /// viz[i] -> daca am vizitat nodul
int N,M;

void read()
{
    scanf("%d%d",&N,&M);
    int a,b;
    for(int i = 1; i <= M; ++i)
    {
        scanf("%d%d",&a,&b);
        Graf[a].Push_back(element(b));
        Graf[b].Push_back(element(a));
    }
}

void DFS(int k){
    viz[k] = 1;
    for(nod *i = Graf[k].Begin; i; i = i->next)
        if(!viz[i->e.inf])
            DFS(i->e.inf);
}

void solve()
{
    int ncc = 0;
    for(int i = 1; i <= N; ++i)
        if(!viz[i])
        {
            DFS(i);
            ++ncc;
        }
    printf("%d\n",ncc);
}

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

    read();
    /**for(nod *i = Graf[1].Begin; i; i = i->next)
        printf("%d ",i->e.inf);
    */
    solve();
    return 0;
}