Cod sursa(job #1570804)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 16 ianuarie 2016 20:52:52
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstring>

using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");

const int MAX_N = 100000;

int n, m, ind, nscc;
int lowLink[1 + MAX_N];
int Index[1 + MAX_N];
bool onStack[1 + MAX_N];
vector < int > adjList[1 + MAX_N];
vector < vector < int > > scc;
stack < int > S;

void dfsSCC(int u) {
    Index[u] = lowLink[u] = ind;
    ind++;
    S.push(u);
    onStack[u] = true;

    for(auto i : adjList[u]) {
        if(Index[i] == -1) {
            dfsSCC(i);
            lowLink[u] = min(lowLink[u], lowLink[i]);
        }
        else if(onStack[i]) {
            lowLink[u] = min(lowLink[u], Index[i]);
        }
    }

    if(lowLink[u] == Index[u]) {
        scc.resize(nscc + 1);
        scc[nscc].push_back(u);
        while(S.top() != u) {
            scc[nscc].push_back(S.top());
            onStack[S.top()] = false;
            S.pop();
        }
        S.pop();
        nscc++;
    }
}

void getSCC() {
    memset(Index, -1, sizeof(Index));
    memset(lowLink, -1, sizeof(lowLink));
    for(int i = 1, ind = 0; i <= n; i++) {
        if(Index[i] == -1) {
            dfsSCC(i);
        }
    }
}

int main() {
    int i, u, v;

    in >> n >> m;
    for(i = 1; i <= m; i++) {
        in >> u >> v;
        adjList[u].push_back(v);
    }

    getSCC();
    out << nscc << '\n';
    for(i = 0; i < nscc; i++) {
        for(auto j : scc[i]) {
            out << j << ' ';
        }
        out << '\n';
    }

    return 0;
}