Cod sursa(job #2286076)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 19 noiembrie 2018 19:48:16
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fi("ctc.in");
ofstream fo("ctc.out");

const int N = 1e5 + 5;

vector<int> g[N];
int lvl[N], low[N];
bool gws[N], instk[N];

vector<vector<int>> ctc;
vector<int> stk;
int n, m, tid;

static void dfs(int u) {
	stk.push_back(u);
	instk[u] = 1;
	gws[u] = 1;
	lvl[u] = low[u] = ++tid;

	for (auto v: g[u]) {
		if (!gws[v])
			dfs(v);
		if (instk[v])
			low[u] = min(low[u], low[v]); }

	if (low[u] == lvl[u]) {
		ctc.emplace_back();
		while (stk.back() != u) {
			ctc.back().push_back(stk.back());
			stk.pop_back(); }
		stk.pop_back();
		ctc.back().push_back(u); } }

int main() {
	fi >> n >> m;
	for (int a, b, i = 1; i <= m; ++i) {
		fi >> a >> b;
		g[a].push_back(b); }

	for (int i = 1; i <= n; ++i)
		if (!gws[i])
			dfs(i);

	fo << ctc.size() << '\n';
	for (auto &c: ctc) {
		for (auto i: c)
			fo << i << ' ';
		fo << '\n'; }
	
	return 0; }