Cod sursa(job #3278981)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 21 februarie 2025 16:49:30
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.05 kb
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

void start() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cout << setprecision(12) << fixed;
    srand(time(nullptr));
    freopen("ctc.in", "r", stdin); freopen("ctc.out", "w", stdout);
}


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

void read() {
    cin>>n>>m;

    gr.resize(n+1);
    int a, b;
    for (int i=0; i<m; i++){
        cin>>a>>b;
        gr[a].push_back(b);
    }
}


int curr_idx = 0;
vector<int> idx;
vector<int> lowlink;
vector<bool> on_s;

vector<vector<int>> ans;
stack<int> s;

void tarjan(int node){
    curr_idx ++;
    idx[node] = curr_idx;
    lowlink[node] = curr_idx;
    s.push(node);
    on_s[node] = true;

    for (auto &x : gr[node]){
        if (!on_s[x]){
            // not visited
            tarjan(x);
            lowlink[node] = min(lowlink[node], lowlink[x]);
        }
        else if (on_s[x]){
            // x in stack (otherwise it is part of another SCC (CTC) -> should be ignored)
            lowlink[node] = min(lowlink[node], lowlink[x]);
        }
    }

    if (idx[node] == lowlink[node]){
        // node is the "root" of the SCC (CTC)
        vector<int> curr_ans;
        while (!s.empty()){
            int w = s.top();
            s.pop();
            //on_s[w] = false;
            curr_ans.push_back(w);
            if (w == node){
                break;
            }
        }
        ans.push_back(curr_ans);
    }

}


void solve() {
    read();

    idx.resize(n+1, 0);
    lowlink.resize(n+1, 0);
    on_s.resize(n+1, false);

    for (int i=1; i<=n; i++){
        if (!idx[i]){
            curr_idx = 0;
            tarjan(i);
        }
    }

    cout<<ans.size()<<'\n';
    for (auto &x : ans){
        for (auto &y : x){
            cout<<y<<" ";
        }
        cout<<'\n';
    }

}



int main(){
    start();

    int t = 1;
    // cin>>t;

    for (int i=1; i<=t; i++){
        solve();
    }

    return 0;
}