Cod sursa(job #1332502)

Utilizator bullseYeIacob Sergiu bullseYe Data 2 februarie 2015 09:19:16
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <vector>
#define DMAX 100001
using namespace std;

vector <int> A[DMAX];
int C[DMAX];
int n, m, nrc;
bool viz[DMAX];
void citire();
void BFS(int);
void afisare();

int main()
{
    int i;
    citire();
    for (i=1; i<=n; ++i)
        if (!viz[i])//face parte din alta parte conexa
            BFS (i);
    afisare();
    return 0;
}

void citire()
{
    int i, x, y;
    FILE*fin=fopen ("dfs.in", "r");
    fscanf(fin, "%d %d", &n, &m);
    for (i=1; i<=m; ++i)
    {
        fscanf(fin, "%d %d", &x, &y);
        A[x].push_back(y);
        A[y].push_back(x);
    }
    fclose(fin);
    return;
}

void BFS (int vf_start)
{
    int prim, ultim, p, i;
    C[1]=vf_start; viz[vf_start]=true;//l-am vizitat
    ++nrc;

    prim=ultim=1;
    while (prim<=ultim)
    {
        //extrag un element din coada
        p=C[prim++];
        //vizitez toti vecinii lui p
        for (i=0; i<A[p].size(); ++i)
            if (!viz[A[p][i]])
            {
                viz[A[p][i]]=true;
                C[++ultim]=A[p][i];
            }
    }
    return;
}

void afisare()
{
    FILE*fout=fopen ("dfs.out", "r");
    fprintf(fout, "%d\n", nrc);
    fclose(fout);
    return;
}