Pagini recente » Cod sursa (job #2799749) | Cod sursa (job #2812620) | Cod sursa (job #2597881) | Cod sursa (job #361739) | Cod sursa (job #2799486)
#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;
std::vector<std::forward_list<int>> ret;
template <bool variant>
void
dfs (int nod) {
viz[variant][nod] = true;
for (int to: edges[variant][nod])
if (!viz[variant][to])
dfs<variant>(to);
if (variant == 0)
usefull.emplace(nod);
else
ret.back().emplace_front(nod + 1);
}
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]) {
ret.emplace_back();
dfs<1>(i);
}
}
printf("%zu\n", ret.size());
for (const auto& list: ret) {
for (int v: list)
printf("%d ", v);
putchar('\n');
}
}