Cod sursa(job #2189280)

Utilizator MaligMamaliga cu smantana Malig Data 27 martie 2018 22:30:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.1 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 = 5e2 + 5;
const ll inf_ll = 1e18 + 5;
const int inf_int = 1e9 + 5;
const int mod = 100003;
const double eps = 1e-7;
using zint = int;

void buildStack(int node, stack<int>& st, vector<bool>& inStack, vector<int>* const adj) {
    inStack[node] = true;

    for (int nxt : adj[node]) {
        if (inStack[nxt]) {
            continue;
        }

        buildStack(nxt, st, inStack, adj);
    }

    st.push(node);
}

void buildComp(int node, const int nrComp, vector<int>& compOf, vector<int>& comp, vector<int>* const adj) {
    compOf[node] = nrComp;
    comp.pb(node);

    for (int nxt : adj[node]) {
        if (compOf[nxt]) {
            continue;
        }

        buildComp(nxt, nrComp, compOf, comp, adj);
    }
}

int main() {
    int N,M;
    in >> N >> M;
    //M = N*(N-1)/2;

    vector<bool> inStack(N+1, false);
    vector<int> compOf(N+1, 0),comp[N+1], adj[N + 1], rev[N + 1];
    int nrComp = 0;

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

        adj[x].pb(y);
        rev[y].pb(x);
    }

    stack<int> st;
    for (int i = 1;i <= N;++i) {
        if (inStack[i]) {
            continue;
        }

        buildStack(i, st, inStack, adj);
    }

    while (st.size()) {
        int node = st.top(); st.pop();
        if (compOf[node]) {
            continue;
        }

        ++nrComp;
        buildComp(node, nrComp, compOf, comp[nrComp], rev);
    }

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

    return 0;
}