Cod sursa(job #870017)

Utilizator exclamatieDica Florin Sebastian exclamatie Data 2 februarie 2013 18:51:02
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>

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

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