Cod sursa(job #1289142)

Utilizator pincucatalinPincu Catalin pincucatalin Data 9 decembrie 2014 15:56:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>

using namespace std;
FILE *in=fopen ("dfs.in","r");
FILE *out=fopen ("dfs.out","w");
int n,m,lst[100001],vf[200001],urm[200001],contor;

bool vizitat[100001];

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

void dfs (int x)
{
    int p,y;
    vizitat[x] = true;
    p=lst[x];
    while (p!=0)
    {
        y=vf[p];
        if(!vizitat[y])
            dfs(y);
        p=urm[p];
    }
}
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);
    }
    for (int i=1;i<=n;i++)
    {
        if (!vizitat[i])
        {
            dfs(i);
            contor++;
        }
    }
    fprintf(out,"%d",contor);
}
int main()
{
    citire();
    return 0;
}