Cod sursa(job #201967)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 5 august 2008 13:11:37
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <iostream>
# define MAX 100001

using namespace std;

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

typedef struct nod
{
    int inf;
    nod * adr;
} *pnod;
pnod sir[MAX];

int n,m,verif[MAX];
int niv;

void baga(int a,int b)
{
    pnod x=new nod;
    x->inf=a;
    x->adr=sir[b];
    sir[b]=x;
}

void citire()
{
    int a,b;
    fin>>n>>m;
    for (int i=0;i<=n;i++)
        sir[i]=NULL;

    for (int i=0;i<m;i++)
    {
        fin>>a>>b;
        baga(a,b);
        baga(b,a);
    }
    memset(verif,0,sizeof(verif));
}

void DF(int poz)
{
    verif[poz]=1;
    pnod x=sir[poz];
    while (x)
        if (verif[x->inf]==0)
            DF(x->inf);
        else
        x=x->adr;
}


int main ()
{
    citire();
    for (int i=1;i<=n;i++)
    if (verif[i]==0)
    {
        niv++;
        DF(i);
    }
    cout<<niv;
    return  0;
}