Cod sursa(job #2896396)

Utilizator matthriscuMatt . matthriscu Data 29 aprilie 2022 22:39:06
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 100005

vector<int> G[NMAX];
stack<int> st;
int idx = 0, order[NMAX], low[NMAX];
bool on_stack[NMAX];
vector<vector<int>> ans;

void tarjan(int node) {
	order[node] = low[node] = ++idx;
	st.push(node);
	on_stack[node] = 1;

	for (const int &neigh : G[node])
		if (!order[neigh]) {
			tarjan(neigh);
			low[node] = min(low[neigh], low[node]);
		} else if (on_stack[neigh])
			low[node] = min(low[neigh], low[node]);

	if (low[node] == order[node]) {
		ans.push_back({});
		int curr;
		do {
			curr = st.top();
			st.pop();
			on_stack[curr] = 0;
			ans.back().push_back(curr);
			low[curr] = low[node];
		} while (curr != node);
	}
}

int main() {
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);

	int n, m;
	scanf("%d%d", &n, &m);

	for (int i = 1, x, y; i <= m; ++i) {
		scanf("%d%d", &x, &y);
		G[x].push_back(y);
	}

	for (int i = 1; i <= n; ++i)
		if (!order[i])
			tarjan(i);

	printf("%ld\n", ans.size());
	for (const vector<int> &v : ans) {
		for (const int node : v)
			printf("%d ", node);
		puts("");
	}
}