Cod sursa(job #3310265)

Utilizator CarenaMironov Cezar Luca Carena Data 12 septembrie 2025 14:58:44
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

const int NMAX=1e5+5;
int n, m, t, ncc, viz[NMAX], dtime[NMAX], rtime[NMAX];
vector<int> adj[NMAX], scc[NMAX];
stack<int> st;

void DFS(int u)
{
    viz[u]=1;
    st.push(u);
    dtime[u]=(t++);
    rtime[u]=dtime[u];
    
    for(auto v:adj[u])
    {
        if(viz[v]==0)
            DFS(v);
        if(viz[v]!=3)
            rtime[u]=min(rtime[u], rtime[v]);
    }
    
    if(dtime[u]==rtime[u])
    {
        ncc++;
        int c=0;
        while(c!=u)
        {
            c=st.top(); st.pop();
            scc[ncc].push_back(c);
            viz[c]=3;
        }
    }
    viz[u]=max(viz[u], 2);
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a, b; cin>>a>>b;
        adj[a].push_back(b);
    }
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
            DFS(i);

    cout<<ncc<<'\n';
    for(int i=1;i<=ncc;i++, cout<<'\n')
        for(auto u:scc[i])
            cout<<u<<" ";
    return 0;
}