Cod sursa(job #2778012)

Utilizator cyg_dawidDavid Ghiberdic cyg_dawid Data 27 septembrie 2021 12:38:57
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

std::ifstream fin ("ctc.in");
std::ofstream fout ("ctc.out");

int const nmax = 100000;
std::vector <std::vector <int>> adj;
std::vector <std::vector <int>> ans;
int cntans;
std::stack <int> st;
bool inStack[nmax + 5];
int lvl[nmax + 5];
int minlvl[nmax + 5];
int level = 1;

void solve (int x) {
    lvl[x] = level++;
    minlvl[x] = lvl[x];
    inStack[x] = true;
    st.push (x);
    int lim = adj[x].size();
    for (int i = 0; i < lim; i++) {
        if (lvl[adj[x][i]] == 0) {
            solve (adj[x][i]);
            minlvl[x] = std::min (minlvl[x], minlvl[adj[x][i]]);
        } else if (inStack[adj[x][i]])
            minlvl[x] = std::min (minlvl[x], lvl[adj[x][i]]);
    }

    if (lvl[x] == minlvl[x]) {
        ans.push_back({});
        while (!st.empty() && st.top() != x) {
            ans[cntans].push_back(st.top());
            inStack[st.top()] = false;
            st.pop();
        }
        if (!st.empty()) {
            ans[cntans].push_back(st.top());
            inStack[st.top()] = false;
            st.pop();
        }
        cntans++;
    }
}

int main()
{
    int n, m;
    fin >> n >> m;
    adj.resize (n + 1);
    for (int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
    }
    for (int i = 1; i <= n; i++)
        if (lvl[i] == 0)
            solve (i);
    fout << cntans << "\n";
    for (int i = 0; i < cntans; i++) {
        int lim = ans[i].size();
        for (int j = 0; j < lim; j++)
            fout << ans[i][j] << " ";
        fout << "\n";
    }
    return 0;
}