Cod sursa(job #2815205)

Utilizator rapidu36Victor Manz rapidu36 Data 9 decembrie 2021 11:55:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int N = 1e5;

int cc[N+1], n, m, ncc;
size_t poz[N+1];
vector <int> a[N+1];//listele de adiacenta
vector <int> c[N+1];//componentele conexe
ifstream in;
ofstream out;

int primul_vecin_nevizitat(int x)
{
    while (poz[x] < a[x].size() && cc[a[x][poz[x]]] != 0)//caut primul vecin al lui x cu cc nul
    {
        poz[x]++;
    }
    if (poz[x] < a[x].size())
    {
        int y = a[x][poz[x]++];
        return y;
    }
    return 0;
}

void dfs_it(int x)
{
    stack <int> stiva;
    cc[x] = ncc;
    stiva.push(x);
    while (!stiva.empty())
    {
        x = stiva.top();
        int y = primul_vecin_nevizitat(x);
        if (y == 0)
        {
            stiva.pop();
        }
        else
        {
            cc[y] = ncc;
            stiva.push(y);
        }
    }
}

void dfs_rec(int x)
{
    cc[x] = ncc;
    for (auto y: a[x])
    {
        if (cc[y] == 0)
        {
            dfs_rec(y);
        }
    }
}

void componente_conexe()
{
    for (int i = 1; i <= n; i++)
    {
        c[cc[i]].push_back(i);
    }
    for (int i = 1; i <= ncc; i++)
    {
        for (auto x: c[i])
        {
            out << x << " ";
        }
        out << "\n";
    }
}

int main()
{
    in.open("dfs.in");
    out.open("dfs.out");
    in >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        in >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }

    for (int i = 1; i <= n; i++)
    {
        if (cc[i] == 0)
        {
            ++ncc;
            dfs_it(i);
            //dfs_rec(i);
        }
    }
    out << ncc << "\n";
    //componente_conexe();
    in.close();
    out.close();
    return 0;
}