Cod sursa(job #1814523)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 24 noiembrie 2016 09:33:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h>
#include <stdlib.h>
int nr,nr_conexe,lista[100001],nod[200001],next[200001],mark[100001];
void add(int x,int y)
{
    nr++;
    nod[nr]=y;
    next[nr]=lista[x];
    lista[x]=nr;
}
void dfs(int x)
{
    int k;
    k=lista[x];
    mark[x]=nr_conexe;
    while(k)
    {
        if(mark[nod[k]]==0)
            dfs(nod[k]);
        k=next[k];
    }
}
int main()
{
    int i,n,m,x,y;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    nr_conexe=0;
    for(i=1; i<=n; i++)
        if(mark[i]==0)
        {
            nr_conexe++;
            dfs(i);
        }
    printf("%d\n",nr_conexe);

    return 0;
}