Cod sursa(job #3296955)

Utilizator OvidRata Ovidiu Ovid Data 19 mai 2025 12:47:10
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.67 kb
#include<bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")


string numeFisier="ctc";
ifstream fin(numeFisier+".in"); ofstream fout(numeFisier+".out");
#define cin fin
#define cout fout


#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll






// An instance of this struct must be instantiated manually 
struct StronglyConnectedComponents{

    int n,m;
    vector< vector<int> > g;


    int indexArray0=0;
    vector<int> indexArray;
    vector<int> lowlink;

    vector<bool> onStack;
    stack<int> st;

    vector< vector<int> > componentOfRepresentative;
    vector<int> representative;


    //Strongly connected components in reverse topological order
    vector< vector<int> > stronglyConnectedComponents;


    //CondensationGraph
    vector< vector<int> > condensationGraph;


    void getNM(int N, int M){
        n =N;
        m = M;
        g.assign(n+10, {});
        indexArray.assign(n+10, 0);
        lowlink.assign(n+10, 0);
        onStack.assign(n+10, 0);
    }

    void strongConnected(int u){
        
        indexArray0++;
        indexArray[u] =indexArray0;
        lowlink[u] = indexArray0;

        st.push(u);
        onStack[u]=true;

        for(int v:g[u]){
            if(!indexArray[v]){
                strongConnected(v);
                lowlink[u]=min(lowlink[u], lowlink[v]);
            }
            else{
                if( onStack[v] ){
                    lowlink[u] = min(lowlink[u], lowlink[v]);
                }
            }
        }
        if( lowlink[u]==indexArray[u] ){
            stronglyConnectedComponents.pb({});
            
            while(st.top()!=u ){
                onStack[st.top()]=false;
                stronglyConnectedComponents.back().pb(st.top());
                st.pop();
            }

            stronglyConnectedComponents.back().pb(u);
            st.pop();
            onStack[u]=false;

        }
    }



    void buildStronglyConnectedComponents(){
        if(!stronglyConnectedComponents.empty()){
            return;
        }
        for(int i=1; i<=n; i++){
            if(indexArray[i]==0){
                strongConnected(i);
            }
        }
    }



    void buildCondensationGraph(){
        buildStronglyConnectedComponents();
        if( !condensationGraph.empty() ){
            return;
        }   
        representative.assign(n+10, 0);
        componentOfRepresentative.assign(n+10, {});
        
        for(auto component: stronglyConnectedComponents){
            int repr = component[0];
            for(auto u : component){
                representative[u]=repr;
            }
            componentOfRepresentative[repr]=component;
        }

    };

} scc;


void input(){
    
    cin>>scc.n>>scc.m;
    scc.getNM(scc.n,scc.m);
    
    for(int i=1,u,v; i<=scc.m; i++){
        cin>>u>>v;
        scc.g[u].pb(v);
    }



}


void solve(){
    scc.buildStronglyConnectedComponents();
}


void output(){
    cout<<scc.stronglyConnectedComponents.size()<<"\n";
    for(auto component: scc.stronglyConnectedComponents){
        for(auto u : component){
            cout<<u<<" ";
        }
        cout<<"\n";
    }
}

int32_t main(){
    INIT

    input();

    solve();

    output();


    return 0;
}