Cod sursa(job #2895697)

Utilizator matthriscuMatt . matthriscu Data 29 aprilie 2022 13:28:49
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 100005

void tarjan(int node, vector<int> *G, stack<int> &st, int &index, int *indices, int *lowlink, bool *on_stack, vector<vector<int>> &ans) {
	indices[node] = lowlink[node] = ++index;
	st.push(node);
	on_stack[node] = 1;
	for (const int &neigh : G[node])
		if (!indices[neigh]) {
			tarjan(neigh, G, st, index, indices, lowlink, on_stack, ans);
			lowlink[node] = min(lowlink[neigh], lowlink[node]);
		} else if (on_stack[neigh])
			lowlink[node] = min(lowlink[neigh], lowlink[node]);
	
	if (lowlink[node] == indices[node]) {
		ans.push_back({});
		int curr;
		do {
			curr = st.top();
			st.pop();
			on_stack[curr] = 0;
			ans.back().push_back(curr);
		} while (curr != node);
	}
}

int main() {
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	
	int n, m;
	scanf("%d%d", &n, &m);

	vector<int> G[NMAX];

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

	stack<int> st;

	int index = 1, indices[NMAX] {}, lowlink[NMAX] {};
	bool visited[NMAX] {}, on_stack[NMAX] {};
	vector<vector<int>> ans;

	for (int i = 1; i <= n; ++i)
		if (!indices[i])
			tarjan(i, G, st, index, indices, lowlink, on_stack, ans);

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