Pagini recente » Cod sursa (job #2325306) | Cod sursa (job #1947851) | Cod sursa (job #1877179) | Cod sursa (job #3267123) | Cod sursa (job #2198637)
#include <bits/stdc++.h>
#define N 100001
using namespace std;
int low[N], ind[N], c_index;
bool in_stack[N];
vector<int> G[N];
vector<vector<int>> sol;
stack<int> S;
void DFS(int s) {
ind[s] = ++c_index;
low[s] = c_index;
S.push(s);
in_stack[s] = true;
for (int &x : G[s])
if (!ind[x]) {
DFS(x);
low[s] = min(low[s], low[x]);
} else if (in_stack[x]) // x is in the same SCC as s
low[s] = min(low[s], ind[x]);
if (low[s] == ind[s]) // pop SCC from stack
{
int x;
vector<int> comp;
do {
x = S.top();
S.pop();
in_stack[x] = false;
comp.push_back(x);
} while (x != s);
sol.push_back(comp);
}
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n, m, x, y;
scanf("%i%i", &n, &m);
while (m--) {
scanf("%i%i", &x, &y);
G[x].push_back(y);
}
for (int i = 1; i <= n; i++)
if (!ind[i])
DFS(i);
// print solution
printf("%lu\n", sol.size());
for (auto &v : sol) {
for (int &x : v) printf("%i ", x);
printf("\n");
}
return 0;
}