Cod sursa(job #1053451)

Utilizator TheNechizFMI Razvan Birisan TheNechiz Data 12 decembrie 2013 19:19:34
Problema Parcurgere DFS - componente conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 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;
}* foo;

foo v[dim];

void Adaug( foo & varf , int x )
{
    foo z = new nod;
    z->val = x;
    z->adr = varf;
    varf = 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 )
{
    foo i;
    t[Gnod] = 1;
    for( i = v[Gnod] ; i ; i = i -> adr )
        if( !t[i->val] )
            DFS(i->val);
}

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

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