Pagini recente » Cod sursa (job #675629) | Cod sursa (job #2409413) | Cod sursa (job #2578665) | Cod sursa (job #2402537) | Cod sursa (job #2799507)
#include <cassert>
#include <cstdio>
#include <vector>
#include <forward_list>
#include <stack>
#define MAXN 100000
std::vector<int> edges[2][MAXN];
bool viz[2][MAXN];
std::stack<int> usefull;
int ret[MAXN];
size_t k = 0;
std::vector<int> sizes;
template <bool variant>
void
dfs (int nod) {
viz[variant][nod] = true;
for (unsigned int i = 0; i != edges[variant][nod].size(); ++ i) {
int to = edges[variant][nod][i];
if (!viz[variant][to])
dfs<variant>(to);
}
if constexpr (variant == 0)
usefull.emplace(nod);
else {
ret[k ++] = nod + 1;
++ sizes.back();
}
}
int main () {
int n, m;
int i;
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d%d", &n, &m);
for (i = 0; i != m; ++ i) {
int de, la;
scanf("%d%d", &de, &la);
-- de, -- la;
edges[0][de].emplace_back(la);
edges[1][la].emplace_back(de);
}
for (i = 0; i != n; ++ i)
if (!viz[0][i])
dfs<0>(i);
while (!usefull.empty()) {
int i = usefull.top();
usefull.pop();
if (!viz[1][i]) {
sizes.emplace_back();
dfs<1>(i);
}
}
printf("%zu\n", sizes.size());
assert(k == n);
k = 0;
for (i = 0; i != sizes.size(); ++ i) {
for (int j = 0; j != sizes[i]; ++ j)
printf("%d ", ret[k ++]);
putchar('\n');
}
}