Cod sursa(job #2000184)

Utilizator mihai.constantinConstantin Mihai mihai.constantin Data 12 iulie 2017 20:47:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream in("dfs.in");
ofstream out("dfs.out");

const int dmax = 100001;

int vf[2*dmax];
int urm[2*dmax];
int lst[dmax];
int nr;

bool viz[dmax];
int NR;

int N, M;

void DFS(int x)
{
    viz[x] = true;

    // PARCURGEM VECINII y AI LUI x

    int p = lst[x];

    while(p)
    {
        int y = vf[p];

        if(viz[y] == false) DFS(y);

        p = urm[p];
    }

}

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

void read()
{
    int x, y;

    in >> N >> M;

    for(int i = 1; i <= M; i++)
    {
        in >> x >> y;

        adauga(x, y);
        adauga(y, x);
    }
}

void solve()
{
    for(int i = 1; i <= N; i++)
        if(!viz[i])
        {
            NR++;
            DFS(i);
        }

    out << NR;
}

int main()
{
    read();
    solve();

    return 0;
}