Pagini recente » Infoarena Monthly 2014 - Runda 8 | Cod sursa (job #722569) | Cod sursa (job #19814) | Cod sursa (job #845979) | Cod sursa (job #2139096)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 100010;
int N, M;
int currTime;
int discoverTime[NMAX], lowLink[NMAX];
bool inStack[NMAX];
vector<int> G[NMAX];
vector<vector<int>> SCC;
stack<int> V;
void dfsTarjan(int node) {
V.push(node);
inStack[node] = 1;
discoverTime[node] = lowLink[node] = currTime++;
for (int it: G[node]) {
if (discoverTime[it] == -1) {
dfsTarjan(it);
lowLink[node] = min(lowLink[node], lowLink[it]);
} else if (inStack[it])
lowLink[node] = min(lowLink[node], discoverTime[it]);
}
if (lowLink[node] == discoverTime[node]) {
int curr;
vector<int> currScc;
do {
curr = V.top();
V.pop();
inStack[curr] = 0;
currScc.push_back(curr);
} while (curr != node);
SCC.push_back(currScc);
}
}
int main() {
assert(freopen("ctc.in", "r", stdin));
assert(freopen("ctc.out", "w", stdout));
memset(discoverTime, -1, sizeof discoverTime);
cin >> N >> M;
while (M--) {
int x, y;
cin >> x >> y;
G[x].push_back(y);
}
for (int i = 1; i <= N; ++i)
if (discoverTime[i] == -1)
dfsTarjan(i);
cout << SCC.size() << '\n';
for (auto i: SCC) {
for (auto j: i)
cout << j << ' ';
cout << '\n';
}
return 0;
}