Pagini recente » Cod sursa (job #1084562) | Cod sursa (job #1250921) | Cod sursa (job #1893028) | Cod sursa (job #296152) | Cod sursa (job #2799492)
#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 (unsigned int i = 0; i != edges[variant][nod].size(); ++ i) {
int to = edges[variant][nod][i];
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);
ret.reserve(MAXN);
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 (unsigned i = 0; i != ret.size(); ++ i) {
for (int v: ret[i])
printf("%d ", v);
putchar('\n');
}
}