Pagini recente » Cod sursa (job #2779800) | Cod sursa (job #577719) | Cod sursa (job #3294358) | Cod sursa (job #3003624) | Cod sursa (job #2884371)
#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;
}