Cod sursa(job #3269092)

Utilizator IleaIlea Bogdan Ilea Data 18 ianuarie 2025 10:52:27
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <stack>
#include <vector>
#include <set>
#include <map>
using namespace std;

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