Cod sursa(job #1570818)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 16 ianuarie 2016 21:05:23
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 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) {
    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++;
        scc[nscc].push_back(u);
        while(S.top() != u) {
            scc[nscc].push_back(S.top());
            onStack[S.top()] = false;
            S.pop();
        }
        S.pop();
    }
}

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