Cod sursa(job #2884371)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 3 aprilie 2022 00:40:38
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.48 kb
#include <bits/stdc++.h>

using namespace std;
vector<int> lowLevel, sccStack, currLevel, whichSCC;
vector<pair<pair<int, vector<int>::iterator>, int> > stackTarjan;
vector<bool> inStack;
vector<vector<int>> scc;
vector<vector<int>> outDegree;
int sccIndex, sccCounter, n, m;
ifstream in("ctc.in");
ofstream out("ctc.out");

void runTarjan(int node) {
    stackTarjan.emplace_back(make_pair(node, outDegree[node].begin()), 0);
    for (; !stackTarjan.empty();) {
        if (stackTarjan.back().second) {
            lowLevel[stackTarjan.back().first.first] = min(lowLevel[stackTarjan.back().first.first],
                                                           lowLevel[*stackTarjan.back().first.second]);
            stackTarjan.back().first.second++;
        }
        if (stackTarjan.back().first.second == outDegree[stackTarjan.back().first.first].begin() &&
            !stackTarjan.back().second) {
            lowLevel[stackTarjan.back().first.first] = ++sccIndex;
            currLevel[stackTarjan.back().first.first] = sccIndex;
            inStack[stackTarjan.back().first.first] = true;
            sccStack.emplace_back(stackTarjan.back().first.first);
        }
        if (stackTarjan.back().first.second != outDegree[stackTarjan.back().first.first].end()) {
            if (!currLevel[*stackTarjan.back().first.second]) {
                stackTarjan.back().second = 1;
                stackTarjan.emplace_back(make_pair(*stackTarjan.back().first.second,
                                                   outDegree[*stackTarjan.back().first.second].begin()), 0);
                continue;
            } else {
                if (inStack[*stackTarjan.back().first.second]) {
                    lowLevel[stackTarjan.back().first.first] = min(lowLevel[stackTarjan.back().first.first],
                                                                   lowLevel[*stackTarjan.back().first.second]);
                }
                stackTarjan.back().first.second++;
                stackTarjan.back().second = 0;
                continue;
            }
        } else {
            if (lowLevel[stackTarjan.back().first.first] == currLevel[stackTarjan.back().first.first]) {
                ++sccCounter;
                int currNode = -1;
                while (currNode != stackTarjan.back().first.first) {
                    currNode = sccStack.back();
                    sccStack.pop_back();
                    inStack[currNode] = false;
                    whichSCC[currNode] = sccCounter;
                    scc[sccCounter].emplace_back(currNode);
                }
            }
            stackTarjan.pop_back();
        }
    }
}


void reduceSCC() {
    sccIndex = 0;
    sccCounter = 0;
    scc.resize(n + 1, vector<int>());
    whichSCC.resize(n + 1, 0);
    lowLevel.resize(n + 1, 0);
    currLevel.resize(n + 1, 0);
    inStack.resize(n + 1, false);
    for (int i = 1; i <= n; ++i) {
        if (!currLevel[i]) {
            runTarjan(i);
        }
    }
    out << sccCounter << '\n';
    for (int i = 1; i <= sccCounter; ++i, out << '\n') {
        for (auto it : scc[i]) {
            out << it << ' ';
        }
    }
    sccIndex = 0;
    sccCounter = 0;
    lowLevel.clear();
    currLevel.clear();
    inStack.clear();
    sccStack.clear();
}


signed main() {
    ios::sync_with_stdio(false);
    in.tie(nullptr);
    int x, y;
    in >> n >> m;
    outDegree.resize(n + 1, vector<int>());
    for (int i = 1; i <= m; ++i) {
        in >> x >> y;
        outDegree[x].emplace_back(y);
    }
    reduceSCC();
    return 0;
}