Cod sursa(job #870020)

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

using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
long int n,m,h; bool s[100001];
struct noda
{
   int inf;
   noda *adr;
}*v[100001];
int citire()
{
    int x,y,l;
    noda *c,*d;
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y;
        for(int 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(int 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(int i=1;i<=n;i++)
    {
        if(!s[i])
        {dfs(i); h++;}
    }out<<h;
}