Cod sursa(job #3331443)

Utilizator coco11coraline kalbfleisch coco11 Data 28 decembrie 2025 11:47:32
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj;
vector<int> disc;
vector<int> low;
vector<bool> inSt;
vector<vector<int>> res;
stack<int> st;
int timer;

void dfs(int n){
    st.push(n);
    inSt[n]=true;
    timer++;
    disc[n]=timer;
    low[n]=timer;
    for(int v: adj[n]){
        if(disc[v]==-1){
            dfs(v);
            low[n]=min(low[n],low[v]);
        }
        else if(inSt[v]){
            low[n]=min(low[n],disc[v]);
        }
    }
    if(low[n]==disc[n]){
        vector<int> r;
        while((!st.empty()) && st.top()!=n){
            r.push_back(st.top());
            inSt[st.top()]=false;
            st.pop();
        }
        r.push_back(n);
        inSt[n]=false;
        st.pop();
        res.push_back(r);
    }
    return;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    int N,M;cin>>N>>M;
    adj.resize(N,{});
    disc.resize(N,-1);
    low.resize(N);
    inSt.resize(N,false);
    int a,b;
    for(int i=0;i<M;i++){
        cin>>a>>b;a--;b--;
        adj[a].push_back(b);
    }
    timer=0;
    for(int i=0;i<N;i++){
        if(disc[i]==-1){
            dfs(i);
        }
    }
    cout<<res.size()<<'\n';
    for(auto r: res){
        for(auto i: r){
            cout<<i+1<<" ";
        }
        cout<<'\n';
    }
}