Cod sursa(job #1289129)

Utilizator pincucatalinPincu Catalin pincucatalin Data 9 decembrie 2014 15:40:58
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <cstdio>

using namespace std;
FILE *in=fopen ("dfs.in","r");
FILE *out=fopen ("dfs.out","w");
int n,m,lst[100000],vf[200000],urm[200000],contor,vizitat[100000];
void adauga (int x,int y)
{
    vf[++m]=y;
    urm[m]=lst[x];
    lst[x]=m;
}
void dfs (int x)
{
    while (x<=n)
    {
    if (!vizitat[x])
    {
    int p,y;
        p=lst[x];
        while (p!=0)
        {
            y=vf[p];
            vizitat[y]=true;
            p=urm[p];
        }
        contor++;
    }
    x++;
    }
    fprintf(out,"%d",contor);
}
void citire ()
{
    int a;
    fscanf (in,"%d%d",&n,&a);
    for (int i=0;i<a;i++)
    {
    int x,y;
    fscanf (in,"%d%d",&x,&y);
    adauga(x,y);
    adauga(y,x);
    }
    dfs(1);
}
int main()
{
    citire();
    return 0;
}