Cod sursa(job #1700457)

Utilizator AstelonBanica Mihai Astelon Data 10 mai 2016 16:07:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>

using namespace std;

struct lista;

struct elem
{
    int info;
    elem *urm;
    elem()
    {
        info=-1;
        urm=NULL;
    }
    ~elem()
    {
        if(urm!=NULL)
            delete urm;
    }
    friend lista;
};

struct lista
{
    elem *urm,*u;
    lista()
    {
        urm=NULL;
        u=NULL;
    }
    ~lista()
    {
        if(urm!=NULL)
            delete urm;
    }
};

void dfs(lista *l[100001],int i,bool v[100001])
{
    v[i]=true;
    elem *p;
    for(p=l[i]->urm;p!=NULL;p=p->urm)
        if(v[p->info]==0)
            dfs(l,p->info,v);
}

int main()
{
    int n,m,i,nr=0;
    lista *l[100001];
    bool v[100001]={false};
    ifstream f("dfs.in");
    f>>n>>m;
    for(i=1;i<=n;i++)
        l[i]=new lista;
    for(i=0;i<m;i++)
    {
        int x,y;
        f>>x>>y;
        elem *p;
        p=new elem;
        p->info=y;
        if(l[x]->u==NULL)
        {
            l[x]->urm=p;
            l[x]->u=p;
        }
        else
        {
            l[x]->u->urm=p;
            l[x]->u=p;
        }
        p=new elem;
        p->info=x;
        if(l[y]->u==NULL)
        {
            l[y]->urm=p;
            l[y]->u=p;
        }
        else
        {
            l[y]->u->urm=p;
            l[y]->u=p;
        }
    }
    f.close();
    for(i=1;i<=n;i++)
    {
        if(v[i]==0)
        {
            dfs(l,i,v);
            nr++;
        }
    }
    ofstream g("dfs.out");
    g<<nr;
    g.close();
    for(i=1;i<=n;i++)
        delete l[i];
    return 0;
}