Cod sursa(job #1354100)

Utilizator cosminionutCosmin Ionut cosminionut Data 21 februarie 2015 17:27:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
using namespace std;

ofstream g("dfs.out");

int N, M, nr;
bool vizitat[100001];
struct nod{int info; nod *urm;} *li[100001];
nod *p;

void push(nod *&li, int informatie)
{
    p=new nod();
    p->info=informatie;
    p->urm=li;
    li=p;
}
void pop(nod *&li)
{
    p=li;
    li=li->urm;
    delete(p);
}
int top(nod *li)
{
    return li->info;
}
bool gol(nod *li)
{
    if(!li || li->info==0) return true;
    else return false;
}


void DFS(int A)
{
    nod *p;
    vizitat[A]=true;
    while(!gol(li[A]))
    {
        if(!vizitat[top(li[A])])
            DFS(top(li[A]));
        pop(li[A]);
    }
}

int main()
{
    int i, x, y;

    FILE *f; f=fopen("dfs.in", "r");
    fscanf(f, "%d%d", &N, &M);

    for(i=1;i<=M;i++)
    {
        fscanf(f, "%d%d", &x, &y);
        push(li[x], y);
        push(li[y], x);
    }
/*
    for(i=1;i<=N;i++)
    {
        while(!gol(li[i]))
        {
            g<<top(li[i])<<" ";
            pop(li[i]);
        }
        g<<'\n';
    }
*/
    for(i=1;i<=N;i++)
        if(!vizitat[i]) nr++, DFS(i);

    g<<nr;

    return 0;
}