Cod sursa(job #1034928)

Utilizator alexpascadiAlexandru Pascadi alexpascadi Data 18 noiembrie 2013 10:56:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>

using namespace std;

const int N=100001;
const int M=200001;
const int NIL=-1;

struct nod
{
    int val;
    int urm;
};

nod a[2*M];
int list[N],n,m,nr=0;
bool vizitat[N];

void marcheaza(int x)
{
    int y,poz;
    vizitat[x]=1;
    poz=list[x];
    while(poz!=NIL)
    {
        y=a[poz].val;
        if(!vizitat[y]) marcheaza(y);
        poz=a[poz].urm;
    }
}

int main()
{
    FILE *in,*out;
    in=fopen("dfs.in","r");
    out=fopen("dfs.out","w");
    int i,nc=0,x,y;
    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=n;i++) {list[i]=NIL; vizitat[i]=0;}
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d",&x,&y);
        a[nr].val=y;
        a[nr].urm=list[x];
        list[x]=nr++;
        a[nr].val=x;
        a[nr].urm=list[y];
        list[y]=nr++;
    }
    for(i=1;i<=n;i++)
    {
        if(!vizitat[i])
        {
            marcheaza(i);
            nc++;
        }
    }
    fprintf(out,"%d",nc);
    return 0;
}