Cod sursa(job #1385048)

Utilizator Tudordmdaniel marin Tudordm Data 11 martie 2015 17:30:25
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<cstdio>

using namespace std;

int viz[100000],nr,lst[100000],urm[100000],vf[100000],n,m;

void adauga (int x,int y)
{

    ++nr;
    vf[nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
    ++nr;
    vf[nr]=x;
    urm[nr]=lst[y];
    lst[y]=nr;

}

void dfs(int nod)
{
    int y,p;
    viz[nod] = 1;
    p=lst[nod];
    while(p!=0)
    {
        y=vf[p];
        viz[y]=1;
        p=urm[p];

    }
}


int main(){

    int sum=0,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);
        adauga(x,y);

    }

    for (int i=1;i<=n;i++)
    {
        if (viz[i] != 1)
        {
            dfs(i);
            sum++;
        }
    }

    printf("%d",sum);

    return 0;
}