Cod sursa(job #858621)

Utilizator costi_.-.Costinnel costi_.-. Data 19 ianuarie 2013 05:11:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#define nmax 100001
using namespace std;

struct nod_lista{
    int vecin;
    nod_lista *link;
};

nod_lista *G[nmax];
int Viz[nmax];
int N,M,nCmp;

void adauga(int unde,int ce)
{
    nod_lista *q=new nod_lista;

    q->vecin=ce;
    q->link=G[unde];
    G[unde]=q;
}

void citeste()
{
    ifstream f("dfs.in");
    int i,x,y;
    f>>N>>M;
    for(i=1;i<=M;i++)
    {
        f>>x>>y;
        adauga(x,y);
        adauga(y,x);
    }

    f.close();
}

void DFS(int nod)
{
    Viz[nod]=1;
    nod_lista *q=G[nod];

    while(q)
    {
        if(!Viz[q->vecin])
        DFS(q->vecin);

        q=q->link;
    }
}

void rezolva()
{
    int i;
    for(i=1;i<=N;i++)
    if(!Viz[i])
    {
        ++nCmp;
        DFS(i);
    }
}

void scrie()
{
    ofstream g("dfs.out");

    g<<nCmp<<'\n';
    g.close();
}




int main()
{
//    cout << "Hello world!" << endl;
    citeste();
    rezolva();
    scrie();
    return 0;
}