Cod sursa(job #1142882)

Utilizator turbowin120Amarandei-Stanescu Alexandru turbowin120 Data 14 martie 2014 12:55:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <stdio.h>
using namespace std;

int vf[200001], nr=0, urm[200001], lst[200001],cnt=0;
bool viz[100011];
inline void adauga(int x, int y)
{
    ++nr;
    vf[nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
}

void dfs(int x)
{
    viz[x]=true;
    int y,p;
    p=lst[x];
    while (p!=0)
    {
        y=vf[p];
        if(!viz[y]) dfs(y);
        p=urm[p];
    }
}
int main()
{
    int n,m,x,y;
    FILE * in, *out;
    in=fopen ("dfs.in","r");
    out=fopen ("dfs.out","w");
    fscanf(in,"%d%d",&n,&m);

    for(int i=1;i<=m;i++)
    {
        fscanf(in,"%d%d",&x,&y);
        adauga(x,y);
        adauga(y,x);
    }


    for(int i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            dfs(i);
            cnt++;
        }
    }
    fprintf(out,"%d",cnt);

    return 0;
}