Cod sursa(job #1289144)

Utilizator stefanlaculeanuLaculeanu Stefan stefanlaculeanu Data 9 decembrie 2014 16:05:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <stdio.h>

int n, m, lst[100005], vf[200005] , urm [200005] , p ,y;
bool viz[100005];

void add( int x , int y)
{
    vf[++m]=y;
    urm[m]=lst[x];
    lst[x]=m;
}

void citire()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);

    int i, x, y, m;
    scanf("%d %d",&n,&m);

    for (i = 1; i <= m; i++)
    {
        scanf("%d %d",&x,&y);
        add(x, y);
        add(y ,x);
    }
}

void DFS( int x)
{
    int p, y;
    viz[x]=true;
    p=lst[x];
    while(p!=0)
    {
        y=vf[p];
        if(!viz[y])
            DFS(y);
        p=urm[p];
    }
}

int main()
{
    int cnt=0;
    citire();
    int i;
    for (i = 1; i <= n; i++)
        if (!viz[i])
        {
            cnt++;
            DFS(i);
        }
    printf("%d\n",cnt);
    return 0;
}