Cod sursa(job #2190643)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 31 martie 2018 13:39:11
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 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 = 3e6 + 5;
const ll inf_ll = 1e18 + 5;
const int inf_int = 1e9 + 5;
const int mod = 100003;
using zint = int;

void dfs(int node,int& nrComp, vector<bool>& inStack,
         stack<int>& st, vector< vector<int> >& adj, vector< vector<int> >& comp, vector<int>& index, vector<int>& lowlink) {
    static int idx = 0;
    ++idx;
    index[node] = lowlink[node] = idx;
    inStack[node] = true;
    st.push(node);

    for (int nxt : adj[node]) {
        if (index[nxt] == 0) {
            dfs(nxt, nrComp, inStack, st, adj, comp, index, lowlink);
            lowlink[node] = min(lowlink[node], lowlink[nxt]);
        }
        else if (inStack[nxt] != 0) {
            lowlink[node] = min(lowlink[node], index[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() {
    int N,M,nrComp = 0;
    in >> N >> M;
    vector< vector<int> > adj(N+1), comp(N+1);
    vector< int > index(N+1,0),lowlink(N+1,0);
    vector< bool > inStack(N+1, false);

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

        stack<int> st;
        dfs(i, nrComp, inStack, st, adj, comp, index, lowlink);
    }

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

    return 0;
}