Cod sursa(job #326218)

Utilizator IoannaPandele Ioana Ioanna Data 24 iunie 2009 12:49:48
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<stdio.h>
long n,m;
long k;
int v[100010];

struct nod
{
nod *urm;
long info;
};

nod *top[100010];

void InsertBegin(long x,long y)
{
nod *aux;
aux=new nod;
aux->urm=top[x];
aux->info=y;
top[x]=aux;
}

void read()
{
scanf("%ld%ld",&n,&m);
long i,x,y;
for (i=1;i<=m;i++)
    {
     scanf("%ld%ld",&x,&y);
     InsertBegin(x,y);
    }
}

void dfs(long x)
{
if (top[x]==NULL)
   {
    return;
   }
nod *p;
for (p=top[x];p!=NULL;p=p->urm)
    {
     if (!v[p->info])
        {
         dfs(p->info);
         v[p->info]=1;
        }
    }
}

void rez()
{
long i;
for (i=1;i<=n;i++)
    {
     if (!v[i])
        {
         k++;
         dfs(i);
        }
    }
}

int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
read();
rez();
printf("%ld",k);
return 0;
}