Cod sursa(job #3306799)

Utilizator yellowGreenFatu Mihai yellowGreen Data 13 august 2025 20:44:08
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
using vi = vector<int>;
int n,m,index,cnt;
vi G[100005];
vector<vi> ctc;
vi idx,low,viz,inStk,c;
/// low[x] = indexul minim la care poate ajunge din x folosind
///          o singura muchie de intoarcere

stack<int> st;
void tarjan();
void getCtc(int x)
{
    while(!st.empty())
    {
        auto y=st.top();
        st.pop();
        c.push_back(y);
        inStk[y]=0;
        if(x==y)
            break;
    }
    cnt++;
    ctc.push_back(c);
    c.clear();
}
void dfs(int x)
{
    ///fac subarbori
    viz[x]=1;
    st.push(x);
    inStk[x]=1;
    index++;
    idx[x]=low[x]=index;
    for(auto y:G[x])
    {
        if(!viz[y]) /// fiu
            {
                dfs(y);
                low[x]=min(low[x],low[y]);
            }
        else
            if(inStk[y]) /// stramos (back-edge)
                low[x]=min(low[x],idx[y]);
    }
    if(idx[x]==low[x])
        getCtc(x);
}
int main()
{
    cin>>n>>m;
    int x,y;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        G[x].push_back(y);
    }
    idx=vi(n+1,0);
    low=vi(n+1,0);
    viz=vi(n+1,0);
    inStk=vi(n+1,0);
    tarjan();
    cout<<cnt<<"\n";
    for(auto v:ctc)
    {
        for(auto x:v)
            cout<<x<<" ";
        cout<<"\n";
    }
    return 0;
}
void tarjan()
{
    for(int i=1;i<=n;i++)
        if(!viz[i])
            dfs(i);
}