Cod sursa(job #2799507)

Utilizator schizofrenieShallan Davar schizofrenie Data 13 noiembrie 2021 11:59:13
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#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');
	}

}