Cod sursa(job #3342659)

Utilizator iordache_Matei Iordache iordache_ Data 25 februarie 2026 10:27:10
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N=2e5+5;
vector<int> g[N];
int scc[N],tin[N],tout[N];
bool cyc[N];
int timer=0,comp=0;
stack<int> stk;
void dfs(int node)
{
    tin[node]=tout[node]=++timer;
    stk.push(node);
    for(auto v:g[node])
    {
        if(!tin[v]) {dfs(v);tout[node]=min(tout[node],tout[v]);}
        else if(!cyc[v]) tout[node]=min(tout[node],tout[v]);
    }
    if(tin[node]!=tout[node]) return;
    ++comp;
    while(1)
    {
        int u=stk.top();
        stk.pop();
        cyc[u]=1,scc[u]=comp;
        if(u==node) break;
    }
}
signed main()
{
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");
    int n,m;
    cin>>n>>m;
    for(int _=1;_<=m;++_)
    {
        int u,v;cin>>u>>v;
        g[u].pb(v);
    }
    for(int i=1;i<=n;++i)
    {
        if(!scc[i]) dfs(i);
    }
    vector<vector<int>> v(comp+5);
    for(int i=1;i<=n;++i) v[scc[i]].pb(i);
    cout<<comp<<'\n';
    for(int i=1;i<=comp;++i)
    {
        for(auto x:v[i]) cout<<x<<" ";
        cout<<'\n';
    }
}