Cod sursa(job #2536651)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 2 februarie 2020 13:56:37
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
// Testez ceva
 
#include <stack>
#include <vector>
#include <fstream>
 
#define DMAX 100010
 
using std::stack;
using std::vector;
 
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
 
int n, m;
vector<int> ad[DMAX];
 
int id;
stack<int> st;
 
int lvl[DMAX];
int low[DMAX];
bool onStack[DMAX];
 
int nrSol;
vector<int> sol[DMAX];
 
void dfs(int at, int father) {
    st.push(at);
    onStack[at] = true;
    lvl[at] = low[at] = lvl[father] + 1;
 
    for (int i = 0; i < (int) ad[at].size(); i++) {
        int to = ad[at][i];
        if (!lvl[to]) {
            dfs(to, at);
            if (low[to] < low[at])
                low[at] = low[to];
        }
        else if (onStack[to] && low[to] < low[at])
            low[at] = low[to];
    }
 
    if (lvl[at] == low[at]) {
        while (true) {
            int node = st.top();
            st.pop();
 
            onStack[node] = false;
            low[node] = lvl[at];
 
            sol[nrSol].push_back(node);
            if (node == at)
                break;
        }
        nrSol++;
    }
}
 
int main() {
    int a, b;
 
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        fin >> a >> b;
        ad[a].push_back(b);
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (!lvl[i]) {
            if (++cnt == 2)
                while (true);
            dfs(i, 0);
        }
 
    fout << nrSol << '\n';
    for (int i = 0; i < nrSol; i++) {
        for (int j = 0; j < (int) sol[i].size(); j++)
            fout << sol[i][j] << ' ';
        fout << '\n';
    }
 
    fout.close();
    return 0;
}