Cod sursa(job #1570823)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 16 ianuarie 2016 21:07:39
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 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 < int > scc[1 + MAX_N];
stack < int > S;

void dfsSCC(int u) {
    int v;

    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]) {
        nscc++;
        do {
            v = S.top();
            S.pop();

            onStack[v] = false;
            scc[nscc].push_back(v);
        } while(v != u);
    }
}

void getSCC() {
    memset(Index, -1, sizeof(Index));
    memset(lowLink, -1, sizeof(lowLink));
    for(int i = 1; i <= n; i++) {
        if(Index[i] == -1) {
            ind = 0;
            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 = 1; i <= nscc; i++) {
        for(auto j : scc[i]) {
            out << j << ' ';
        }
        out << '\n';
    }

    return 0;
}