Cod sursa(job #656035)

Utilizator fenrigasdFc dd2 fenrig Data 3 ianuarie 2012 20:27:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <stdio.h>


typedef struct Nod
{
    int info;
    Nod *next;
} nod;
nod *v[100010];
int viz[100010],n,m,c;
void create()
{   int x,y;
    nod *p;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        p=new nod;
        p->next=v[x];
        p->info=y;
        v[x]=p;

        p=new nod;
        p->next=v[y];
        p->info=x;
        v[y]=p;


    }
}

void DF(int x)
{
    nod *p;
    viz[x]=1;
    p=v[x];
    while(p!=NULL)
    {
        if(viz[p->info]==0)
        DF(p->info);
        p=p->next;
    }
}
int main()
{
    create();
    for(int i=1;i<=n;i++)
     if(viz[i]==0)
     {
         c++;DF(i);
     }
     printf("%d",c);
}