Cod sursa(job #2343643)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 14 februarie 2019 10:13:01
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <stack>
#include <vector>
#include <fstream>

#define NMAX 100010

using std::stack;
using std::vector;

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

int n, m;
vector<int> ad[NMAX];

int id;
stack<int> st;

int ids[NMAX];
int low[NMAX];
bool onStack[NMAX];

int nrSol;
vector<int> sol[NMAX];

void dfs(int at) {
    st.push(at);
    onStack[at] = true;
    ids[at] = low[at] = ++id;

    for (int i = 0; i < (int) ad[at].size(); i++) {
        int to = ad[at][i];
        if (!ids[to]) {
            dfs(to);
            if (low[to] < low[at])
                low[at] = low[to];
        }
        else if (onStack[to] && low[to] < low[at])
            low[at] = low[to];
    }

    if (ids[at] == low[at]) {
        while (true) {
            int node = st.top();
            st.pop();

            onStack[node] = false;
            low[node] = ids[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);
    }

    for (int i = 1; i <= n; i++)
        if (!ids[i])
            dfs(i);

    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;
}