Pagini recente » Cod sursa (job #408603) | Cod sursa (job #1042402) | Cod sursa (job #3212600) | Cod sursa (job #2881711) | Cod sursa (job #2456610)
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> G[100005];
int cidx = 0;
int idx[100005], low[100005];
stack<int> S;
bool in_stack[100005];
vector<vector<int>> scc;
void tarjan(int node) {
idx[node] = ++cidx;
low[node] = cidx;
in_stack[node] = 1;
S.push(node);
for (auto p : G[node]) {
if (!idx[p]) {
tarjan(p);
low[node] = min(low[node], low[p]);
} else if (in_stack[p]) {
low[node] = min(low[node], idx[p]);
}
}
if (low[node] == idx[node]) {
int u;
scc.push_back(vector<int>());
do {
u = S.top();
S.pop();
in_stack[u] = 0;
scc.back().push_back(u);
} while (u != node);
}
}
int main() {
ios_base::sync_with_stdio(false);
ifstream cin("ctc.in");
ofstream cout("ctc.out");
cin >> n >> m;
int x, y;
while (m--) {
cin >> x >> y;
G[x].push_back(y);
}
for (int i = 1; i <= n; ++i) {
if (!idx[i]) {
tarjan(i);
}
}
cout << scc.size() << "\n";
for (auto v : scc) {
for (auto i : v) cout << i << " ";
cout << "\n";
}
}