Cod sursa(job #1243482)

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

#define Nmax 100050

using namespace std;

class element{
public:
    element(){
        inf = 0;
    }
    element(int x){
        this->inf = x;
    }
    int inf;
};

class nod{
public:
    nod(){
        next = prev = NULL;
    }
    nod(element e,nod *next, nod *prev){
        this->e = e;
        this->next = next;
        this->prev = prev;
    }
    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()){
            Begin = End = new nod(e,0,0);
            return;
        }
        End->next = new nod(e,0,End);
        End = End->next;
    }
    void Push_front(element e){
        if(Empty()){
            Begin = End = new nod(e,0,0);
            return;
        }
        Begin->prev = new nod(e,Begin,0);
        Begin = Begin->prev;
    }
    void Insert(element e, nod *_crt)
    {
        nod *nodc = new nod(e,_crt,_crt->prev);
        _crt->prev->next = nodc;
        _crt->prev = nodc;
    }
};
lista G[Nmax];
int N,M,used[Nmax];

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

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

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

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

    read();
    solve();

    return 0;
}