Cod sursa(job #2345147)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 15 februarie 2019 22:07:53
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 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 ids[NMAX];
int low[NMAX];

int id;
stack<int> st;
bool onStack[NMAX];

int nrComp;
vector<int> comp[NMAX];

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

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

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

            onStack[top] = false;
            low[top] = ids[node];

            comp[nrComp].push_back(top);
            if (top == node)
                break;
        }
        nrComp++;
    }
}

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 << nrComp << '\n';
    for (int i = 0; i < nrComp; i++) {
        for (int j = 0; j < (int) comp[i].size(); j++)
            fout << comp[i][j] << ' ';
        fout << '\n';
    }

    fout.close();
    return 0;
}