Cod sursa(job #1077754)

Utilizator exclamatieDica Florin Sebastian exclamatie Data 11 ianuarie 2014 17:13:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int m,n,h;
bool s[100001];
struct Lista
{
    int inf;
    Lista *adr;
}*v[100001];
int citire()
{
    Lista *d,*c;
    int x,y,l;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y;
        for(int j=1;j<=2;j++)
        {
            if(!v[x])
            {
                v[x]=new(Lista);
                v[x]->inf=x;
                d=new(Lista);
                v[x]->adr=d;
                d->inf=y;
                d->adr=0;
            }
            else
            {
                d=new(Lista);
                d=v[x];
                while(d->adr)
                d=d->adr;
                c=new(Lista);
                d->adr=c;
                c->inf=y;
                c->adr=0;
            }
            l=x;x=y;y=l;
        }

    }
    for(int j=1;j<=n;j++)
    {
        if(!v[j])
        {
            v[j]=new(Lista);
            v[j]->inf=j;
            v[j]->adr=0;
        }
    }

}
inline int dfs(int g)
{
    Lista *p;
    s[g]=1;
    for(p=v[g];p;p=p->adr)
    {
        if(!s[p->inf])
        dfs(p->inf);
    }
}
int main()
{
    in>>n>>m;
    citire();
    for(int g=1;g<=n;g++)
    {
        if(!s[g])
        {
            dfs(g);
            h++;
        }
    }
    out<<h;
}