Cod sursa(job #2504150)

Utilizator AlexBosneag26Bosneag Alexandru AlexBosneag26 Data 4 decembrie 2019 15:40:52
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>

using namespace std;

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

int vf[200001], lst[100001], urm[100001], viz[100001], nr;

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

void dfs(int x)
{
    viz[x] = true;
    for(int p = lst[x]; p != 0; p = urm[p])
    {
        int y = vf[p];
        if(!viz[y])
            dfs(y);
    }
}

int main()
{
    int n, m, x, y, c = 0;
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        in >> x >> y;
        adauga(x,y);
        adauga(y,x);
    }
    for(int i = 1; i <= n; i++)
        {
            if(!viz[i])
                dfs(i), c++;

        }
    out << c;
    return 0;
}