Cod sursa(job #2190645)

Utilizator MaligMamaliga cu smantana Malig Data 31 martie 2018 13:45:56
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <bits/stdc++.h>

using namespace std;

#if 1
    #define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
    #define pn cout<<endl
#else
    #define pv(x)
    #define pn
#endif

#ifdef ONLINE_JUDGE
    #define in cin
    #define out cout
#else
    ifstream in("ctc.in");
    ofstream out("ctc.out");
#endif

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
#define pb push_back
#define mp make_pair
const int NMax = 1e5 + 5;
const ll inf_ll = 1e18 + 5;
const int inf_int = 1e9 + 5;
const int mod = 100003;
using zint = int;

int N,M,nrComp;
vector<bool> inStack(NMax , false);
vector<int> index(NMax, 0),lowlink(NMax), comp[NMax], adj[NMax];
stack<int> st;

void dfs(int node) {
    static int idx = 0;
    ++idx;
    index[node] = lowlink[node] = idx;
    inStack[node] = true;
    st.push(node);

    for (int nxt : adj[node]) {
        if (!index[nxt]) {
            dfs(nxt);
            lowlink[node] = min(lowlink[node], lowlink[nxt]);
        }
        else if (inStack[nxt]) {
            lowlink[node] = min(lowlink[node], lowlink[nxt]);
        }
    }

    if (index[node] == lowlink[node]) {
        ++nrComp;
        int curr = 0;

        do {
            curr = st.top();
            st.pop();

            comp[nrComp].pb(curr);
            inStack[curr] = false;
        } while (curr != node);
    }
}

int main() {
    in >> N >> M;

    for (int i = 1;i <= M;++i) {
        int x,y;
        in >> x >> y;

        adj[x].pb(y);
    }

    for (int i = 1;i <= N;++i) {
        if (index[i]) {
            continue;
        }

        dfs(i);
    }

    out << nrComp << '\n';
    for (int i = 1;i <= nrComp;++i) {
        for (int node : comp[i]) {
            out << node << ' ';
        }
        out << '\n';
    }

    return 0;
}