Cod sursa(job #897252)

Utilizator DanFodorFODOR Dan Horatiu DanFodor Data 27 februarie 2013 19:39:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>

using namespace std;

struct nod {
    int info;
    nod *next;} *prim[100007], *aux, *p;

int st[100007], v[100007];

int main()
{
    int n, m;
    ifstream in ("dfs.in");
    ofstream out ("dfs.out");
    in>>n>>m;
    int i, a, b;
    for (i=1; i<=m; i++)
    {
        in>>a>>b;
        aux=new nod;
        aux->info=a;
        aux->next=prim[b];
        prim[b]=aux;
        aux=new nod;
        aux->info=b;
        aux->next=prim[a];
        prim[a]=aux;
    }
    /*for (i=1; i<=n; i++)
    {
        out<<i<<": ";
        for (p=prim[i]; p; p=p->next)
            out<<p->info<<" ";
        out<<"\n";
    }*/

    int k=0, f, ok;
    for (i=1; i<=n; i++)
        if (v[i]==0)
        {
            k++;
            f=1;
            v[i]=k;
            st[f]=i;
            while (f>0)
            {
                ok=0;
                for (p=prim[st[f]]; p; p=p->next)
                    if (!v[p->info])
                    {
                        v[p->info]=k;
                        st[++f]=p->info;
                        ok=1;
                    }
                if (!ok)
                    f--;
            }
        }
    out<<k;
    return 0;
}