Cod sursa(job #3342709)

Utilizator amunnumeVlad Patrascu amunnume Data 25 februarie 2026 12:55:08
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int N=1e5+1;
int n,m,i,j,x,y,sz,low[N],in[N];
bool onStack[N];
vector<int> edge[N],comp[N];
stack<int> s;
void read()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y;
        edge[x].push_back(y);
    }
}
void pop_stack(int last)
{
    sz++;
    int x;
    do
    {
        x=s.top();
        s.pop();
        comp[sz].push_back(x);
        onStack[x]=0;
    }while(x!=last);
}
void dfs(int x)
{
    static int time=0;
    in[x]=low[x]=++time;
    onStack[x]=1;
    s.push(x);
    for(auto y:edge[x])
    {
        if(!in[y])
        {
            dfs(y);
            low[x]=min(low[x],low[y]);
        }
        else if(onStack[y])
        {
            low[x]=min(low[x],in[y]);
        }
    }
    if(low[x]==in[x])
        pop_stack(x);
}
void parc()
{
    for(int i=1;i<=n;++i)
    {
        if(!in[i]) dfs(i);
    }
}
void print()
{
    fout<<sz<<'\n';
    for(int i=1;i<=sz;++i)
    {
        for(auto x:comp[i])
            fout<<x<<' ';
        fout<<'\n';
    }
}
int main()
{
    read();
    parc();
    print();
    return 0;
}