Cod sursa(job #3268958)

Utilizator IleaIlea Bogdan Ilea Data 18 ianuarie 2025 09:55:10
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
//https://infoarena.ro/problema/ctc
#include <iostream>
#include <stack>
#include <vector>
#include <set>
using namespace std;

vector<int> g[1001], rg[1001];
int n;
stack<int> nodes, comp;
bool b[1001];
void dfs(int i, stack<int>& st, 
    const vector<int> graph[])
{
    b[i]=true;
    for (auto it:graph[i]){
        if (!b[it]){
            dfs(it, st, graph);
        }
    }
    st.push(i);
}
vector<set<int>> sol;
void kosaraju(){
    for (int i=1; i<=n; ++i){
        if (!b[i])dfs(i, nodes, g);
    }
    fill(b, b+n+1, false);
    while (!nodes.empty()){
        int i=nodes.top();
        nodes.pop();
        if (!b[i]){
            dfs(i, comp, rg);
            sol.push_back({});
            while (!comp.empty()){
                sol.back().insert(comp.top());
                comp.pop();
            }
        }
    }
}
int main(){
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    int m;
    cin>>n>>m;
    while (m--){
        int x, y;
        cin>>x>>y;
        g[x].push_back(y);
        rg[y].push_back(x);
        //cout<<y<<" - "<<x<<endl;
    }
    kosaraju();
    cout<<sol.size()<<endl;
    for (auto it:sol){
        for (auto jt:it){
            cout<<jt<<" ";
        }
        cout<<"\n";
    }
}