Cod sursa(job #185736)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 25 aprilie 2008 22:55:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>

using namespace std;

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

struct nod
{
    int dir;
    nod* alt_ego;
};
typedef nod *arb;
arb a[100005];
int n,m,sir[1000005],num;

void baga(arb &x,int inf)
{
    arb y;
    y=new nod;
    y->dir=inf;
    y->alt_ego=x;
    x=y;
}

void citire()
{
    fin>>n>>m;
    int x,y;
    for (int i=0;i<m;i++)
    {
        fin>>x>>y;
        baga(a[x],y);
        baga(a[y],x);
    }
}

void parc(int nod)
{
     arb p;
     sir[nod] = 1;
     for (p=a[nod];p; p=p->alt_ego)
            if (!sir[p -> dir])
                 parc(p -> dir);
}

int main ()
{
    citire();
    for (int niv=1;niv<=n;niv++)
        if (!sir[niv])
        {
            num++;
            parc(niv);
        }
    fout<<num<<"\n";
return 0;
}