Cod sursa(job #3335294)

Utilizator Alex283810Mocan Alexandru Vali Alex283810 Data 22 ianuarie 2026 11:06:33
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <bits/stdc++.h>
int disc[100001];
std::vector<std::vector<int>>muchii;
std::vector<std::vector<int>>ans;
std::stack<int>st;
int lowt[100001];
bool in_componenta[100001];
void tarzan(int v)
{
    static int timer = 0; /// valoarea timerului se mentine si dupa reapelare
    disc[v] = lowt[v] = ++timer;
    st.push(v);
    in_componenta[v] = true;

    for(auto next: muchii[v])
    {
        if(disc[next] == -1)
        {
            tarzan(next); /// nu lam gasit pana acum si
            ///nu a fost parte din alta componenta conexa
            lowt[v] = std::min(lowt[v], lowt[next]);
        }
        else if(in_componenta[v] == true)
        {
            lowt[v] = std::min(lowt[v], lowt[next]);
            /// facem updateul acesta fiind nodul cu care
            /// next are cel mai mic dicovery time si cu care este conectat
        }
    }

    if(disc[v] == lowt[v]) /// am ajuns la root
    {
        std::vector<int>c;
        int top;
        do
        {
            c.push_back(st.top());
            in_componenta[st.top()] = false;
            top = st.top();
            st.pop();

        }while(v != top);
        ans.push_back(c);
    }
}
int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    int n, m;
    std::cin >> n >> m;
    muchii.resize(n + 1);
    for(int i = 1; i <= m; i++)
    {
        int a, b;
        std::cin >> a >> b;
        muchii[a].push_back(b);
    }
    for(int i = 1; i <= n; i++)
        disc[i] = -1;///nu au fost descoperite inca

    for(int i = 1; i <= n; i++)
    {
        if(disc[i] == -1)
            tarzan(i);
    }
    std::cout << ans.size() << '\n';
    for(int i = 0; i < ans.size(); i++, std::cout << '\n')
        for(int j = ans[i].size() - 1; j >= 0; --j)
            std::cout << ans[i][j] << ' ';
    return 0;
}