Cod sursa(job #3376653)

Utilizator amunnumeVlad Patrascu amunnume Data 18 noiembrie 2026 19:49:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int N=1e5+5;
struct node
{
    int in,out,low,on_stack;
    vector<int> adj;
    node():in(0),out(0),low(0),on_stack(0) {}
}v[N];
int n,m,i,j,x,y;
stack<int> s;
vector<vector<int>> sol;
void pop_scc(int r)
{
    vector<int> tau;
    int x;
    do
    {
        x=s.top();
        s.pop();
        tau.push_back(x);
        v[x].on_stack=0;

    }while(x!=r);
    sol.push_back(tau);
}
void dfs(int x)
{
    static int time=0;
    v[x].in=v[x].low=++time;
    v[x].on_stack=1;
    s.push(x);
    for(auto y:v[x].adj)
    {
        if(!v[y].in)
        {
            dfs(y);
            v[x].low=min(v[x].low,v[y].low);
        }
        else if(v[y].on_stack)
            v[x].low=min(v[x].low,v[y].in);
    }
    if(v[x].low==v[x].in)
        pop_scc(x);
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y;
        v[x].adj.push_back(y);
    }
    for(i=1;i<=n;++i)
    {
        if(!v[i].in) dfs(i);
    }
    fout<<sol.size()<<'\n';
    for(auto e:sol)
    {
        for(auto f:e)
            fout<<f<<' ';
        fout<<'\n';
    }
    return 0;
}