Cod sursa(job #741329)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 25 aprilie 2012 20:50:48
Problema Parcurgere DFS - componente conexe Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb

#include <fstream>

const unsigned int SIZE(100001);

struct nod
{
    unsigned int value;
    struct nod *next;
} *graf [SIZE];

bool mark [SIZE];

inline void push (struct nod *&first, unsigned int value)
{
    struct nod *new_nod(new struct nod);
    new_nod->value = value;
    new_nod->next = first;
    first = new_nod;
}

void DepthFirstSearch (unsigned int value)
{
    mark[value] = true;
    struct nod *i(graf[value]);
    while (i)
    {
        if (!mark[i->value])
            DepthFirstSearch(i->value);
        i = i->next;
    }
}

int main (void)
{
    unsigned int n,m;
    std::ifstream input("dfs.in");
    input >> n >> m;
    unsigned int x,y;
    do
    {
        input >> x >> y;
        push(graf[x],y);
        push(graf[y],x);
        --m;
    }
    while (m);
    input.close();
    m = 1;
    x = 0;
    do
    {
        if (!mark[m])
        {
            ++x;
            DepthFirstSearch(m);
        }
        ++m;
    }
    while (m <= n);
    std::ofstream output("dfs.out");
    output << x << '\n';
    output.close();
    return 0;
}