Cod sursa(job #2822251)

Utilizator Cosmin2004_InfoMoldoveanu Cosmin Cosmin2004_Info Data 23 decembrie 2021 18:56:12
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;
#ifdef INFOARENA
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define cout fout
#define cin fin
#endif // INFOARENA
vector <vector <int>> g, cc;
stack <int> st;
const int NMAX = 1e5;
int ind[NMAX + 5], low[NMAX + 5], k, cnt;
bool onstack[NMAX + 5];
void dfs(int u) {
    onstack[u] = true;
    st.push(u);
    ind[u] = ++cnt;
    low[u] = ind[u];
    for(int adj : g[u]) {
        if(!ind[adj]) {
            dfs(adj);
            low[u] = min(low[u], low[adj]);
        } else if(onstack[adj]) low[u] = min(low[u], ind[adj]);
    }
    if(low[u] == ind[u]) {
        cc.push_back({u}); k++;
        while(st.top() != u) {
            onstack[st.top()] = false;
            cc[k - 1].push_back(st.top());
            st.pop();
        }
        st.pop();
        onstack[u] = false;
    }
}

int main()
{
    int n, m, u, v;
    cin >> n >> m;
    g.resize(n + 1);
    for(int i = 1; i <= m; i++)
        cin >> u >> v,
        g[u].push_back(v);
    for(int i = 1; i <= n; i++) if(!ind[i])
        dfs(i);
    cout << k << "\n";
    for(int i = 0; i < k; i++, cout << "\n") for(int x : cc[i])
        cout << x << " ";
    return 0;
}