Cod sursa(job #3373417)

Utilizator lea_Lea Ales lea_ Data 6 noiembrie 2026 22:16:23
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> adj[100005];
int tin[100005], low[100005], parent[100005], it[100005];
bool onStack[100005];
int timer_=0;
vector<vector<int>> comps;

void dfs(int s){
    vector<int> st, stk;
    st.push_back(s);
    stk.push_back(s);
    onStack[s]=true;
    tin[s]=low[s]=++timer_;
    parent[s]=0;

    while(!st.empty()){
        int v=st.back();
        if(it[v]<(int)adj[v].size()) {
            int u=adj[v][it[v]++];
            if(!tin[u]){
                parent[u]=v;
                tin[u]=low[u]=++timer_;
                st.push_back(u);
                stk.push_back(u);
                onStack[u]=true;
            } else if (onStack[u]) {
                low[v]=min(low[v],tin[u]);
            }
        } else{
            st.pop_back();
            if (low[v]==tin[v]) {
                vector<int> comp;
                int w;
                do{
                    w=stk.back();
                    stk.pop_back();
                    onStack[w]=false;
                    comp.push_back(w);
                } while (w!=v);
                comps.push_back(comp);
            }
            int p=parent[v];
            if (p) low[p]=min(low[p], low[v]);
        }
    }
}


int main(){
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");

    int n,m;
    fin>>n>>m;

    for(int i=0; i<m; i++){
        int x,y;
        fin>>x>>y;
        adj[x].push_back(y);
    }

    for(int i=1; i<=n; i++)
        if(!tin[i])
            dfs(i);
    
    fout<<comps.size()<<"\n";
    for(int i=0; i<(int)comps.size(); i++){
        for(size_t j=0; j<comps[i].size(); j++)
            fout<<comps[i][j]<<(j+1<comps[i].size()? " " : "\n");
    }
    return 0;
}