Cod sursa(job #1143111)

Utilizator tanduraDomnita Dan tandura Data 14 martie 2014 19:20:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>
using namespace std;

int n,m,nr;
vector<bool> viz;

typedef struct nod
{
    int x;
    nod *a;
} *pNod;

pNod v[100001];

void add(pNod &destinatie,int valoare)
{
    pNod p;
    p = new nod;
    p->x = valoare;
    p->a = destinatie;
    destinatie = p;
}

void citire()
{
    ifstream f("dfs.in");

    f>>n>>m;

    viz.resize(n+1,false);

    int a,b;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b;
        add(v[a],b);
        add(v[b],a);
    }

    f.close();
}

void parcurgere(int nod)
{
    viz[nod]=true;
    for(pNod p=v[nod]; p != NULL ;p=p->a)
        if(!viz[p->x])
            parcurgere(p->x);
}

void rezolvare()
{
    for(int i=1;i<=n;i++)
        if(!viz[i])
        {
            nr++;
            parcurgere(i);
        }
}

void afisare()
{
    ofstream g("dfs.out");
    g<<nr<<"\n";
    g.close();
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}