Cod sursa(job #1053420)

Utilizator TheNechizFMI Razvan Birisan TheNechiz Data 12 decembrie 2013 19:04:03
Problema Parcurgere DFS - componente conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
# include <fstream>
# define dim 100005
using namespace std;

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

int n,m,nr;
bool t[dim];

typedef struct nod
{
    int val;
    nod * adr;
}* tip1;

tip1 v[dim];
tip1 Stiva;

void Adaug( tip1 & varf , int x )
{
    tip1 z = new nod;
    z->val = x;
    z->adr = varf;
    varf = z;
}

void Sterg( tip1 & varf )
{
    tip1 z = varf;
    varf = varf->adr;
    delete z;
}

void Citire()
{
    int i,x,y;
    fin >> n >> m;
    for( i = 1 ; i <= n ; ++i )
    {
        fin >> x >> y;
        Adaug(v[x],y);
        Adaug(v[y],x);
    }
    fin.close();
}

inline void Tipar()
{
    fout << nr;
    fout.close();
}

void DFS( int Gnod )
{
    tip1 i;
    Adaug(Stiva,Gnod);
    while( Stiva )
    {
        Gnod = Stiva->val;
        Sterg(Stiva);
        t[Gnod] = 1;
        for( i = v[Gnod] ; i ; i = i->adr )
            if( !t[i->val] )
                Adaug(Stiva,i->val);
    }
}

void Rezolv()
{
    for( int i = 1 ; i <= n ; ++i )
        if( !t[i] )
        {
            ++nr;
            DFS(i);
        }
}

int main()
{
    Citire();
    Rezolv();
    Tipar();
    return 0;
}