Cod sursa(job #561193)

Utilizator chrissBota Cristian chriss Data 18 martie 2011 23:49:05
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>

int viz[1000005],n,m,cnt;

struct nod{
            int info;
            nod *next;
          };
nod *L[100001];

void add(int x, int y)
{
    nod *p=new nod;
    p->info=y;
    p->next=L[x];
    L[x]=p;
}
void DF(int nd)
{
    viz[nd]=1;
    for(nod *p=L[nd]; p; p=p->next)
        if(!viz[p->info])
            viz[p->info]=1;
}
int main()
{
    int x,y;

    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);
        add(x,y);
        add(y,x);
    }

    for(int i=1; i<=n; ++i)
        if(!viz[i])
        {
            cnt++;
            DF(i);
        }
    printf("%d",cnt);
}