Cod sursa(job #3269802)

Utilizator DARIUSQSSDarius Nicoara DARIUSQSS Data 20 ianuarie 2025 20:45:01
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <bits/stdc++.h>

std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");

int n, m;
std::vector<std::vector<int>> nums;
std::vector<int> minim;
std::vector<int> viz;
std::vector<int> inStack;
std::stack<int> s;
std::vector<std::vector<int>> rez;
int i = 0;

void scc(int node)
{
    viz[node] = minim[node] = i;
    i++;
    s.push(node), inStack[node] = 1;
    for(int x : nums[node])
    {
        if(viz[x] == -1)
        {
            scc(x);
            minim[node] = std::min(minim[node], minim[x]);
        }
        else if(inStack[x])
        {
            minim[node] = std::min(minim[node], minim[x]);
        }
    }

    if(minim[node] == viz[node])
    {
        std::set<int> st;
        int sccCurent = s.top(); s.pop();

        while(sccCurent != node)
        {
            st.insert(sccCurent);
            inStack[sccCurent] = 0;
            sccCurent = s.top(); s.pop();
        }
        st.insert(sccCurent);

        rez.push_back({});
        for(auto it = st.begin(); it != st.end(); it++)
        {
            rez.back().push_back(*it);
        }
    }
}

int main()
{
    fin >> n >> m;
    nums.resize(n + 1, std::vector<int>(0));
    viz.resize(n + 1, -1);
    inStack.resize(n + 1);
    minim.resize(n + 1);
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        nums[x].push_back(y);
    }
    
    for(int i = 1; i <= n; i++)
    {
        std::sort(nums[i].begin(), nums[i].end());
    }


    for(int i = 1; i <= n; i++)
    {
        if(!viz[i])
        {
            scc(1);
        }
    }

    fout << rez.size() << '\n';
    for(auto x : rez)
    {
        for(int y : x)
        {
            fout << y << ' ';
        }
        fout << '\n';
    }

}