Cod sursa(job #3374598)

Utilizator darius_cimbruDarius Cimbru darius_cimbru Data 9 noiembrie 2026 03:30:44
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.78 kb
#include <bits/stdc++.h>
#define N 100001
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

vector<int> vecini[N];
int idx[N];       // al catelea nod vizitat in dfs, 0 = nevizitat
int low[N];       // cel mai mic idx la care ajunge nodul
int urmatorul[N]; // urmatorul[x] = la al catelea vecin al lui x urmeaza sa ma uit
bool pe_stiva[N];
vector<int> stiva; // stiva lui tarjan, cu nodurile inca deschise
vector<vector<int>> componente;
vector<int> componenta;
deque<int> d;
int contor;

int main()
{
    int n, m;
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        f >> x >> y;
        vecini[x].push_back(y);
    }
    for (int radacina = 1; radacina <= n; radacina++)
    {
        if (idx[radacina] != 0)
            continue;
        contor++;
        idx[radacina] = low[radacina] = contor;
        stiva.push_back(radacina);
        pe_stiva[radacina] = 1;
        d.push_back(radacina);
        while (!d.empty())
        {
            int nod_curent = d.back(); //dfs
            if (urmatorul[nod_curent] < vecini[nod_curent].size())
            {
                int vecin = vecini[nod_curent][urmatorul[nod_curent]];
                urmatorul[nod_curent]++;
                if (idx[vecin] == 0) // nevizitat, cobor in el
                {
                    contor++;
                    idx[vecin] = low[vecin] = contor;
                    stiva.push_back(vecin);
                    pe_stiva[vecin] = 1;
                    d.push_back(vecin);
                }
                else if (pe_stiva[vecin]) // arc inapoi spre un nod inca deschis
                    low[nod_curent] = min(low[nod_curent], idx[vecin]);
            }
            else // am terminat toti vecinii lui nod_curent
            {
                d.pop_back();
                if (low[nod_curent] == idx[nod_curent]) // nu pot urca mai sus, deci e radacina de componenta
                {
                    componenta.clear();
                    int nod;
                    do
                    {
                        nod = stiva.back();
                        stiva.pop_back();
                        pe_stiva[nod] = 0;
                        componenta.push_back(nod);
                    } while (nod != nod_curent);
                    componente.push_back(componenta);
                }
                if (!d.empty()) // ma intorc la parinte si ii actualizez low
                {
                    int parinte = d.back();
                    low[parinte] = min(low[parinte], low[nod_curent]);
                }
            }
        }
    }
    g << componente.size() << "\n";
    for (int i = 0; i < componente.size(); i++)
    {
        for (int j = 0; j < componente[i].size(); j++)
            g << componente[i][j] << " ";
        g << "\n";
    }
    f.close();
    g.close();
}