Cod sursa(job #3124233)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 27 aprilie 2023 13:27:41
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;

void dfs(int node, vector<int> &discovery, vector<bool> &in_stack, vector<int> &lowest, stack<int> &s, vector<vector<int>> &adj, vector<vector<int>> &ctcs, int &t) {

	discovery[node] = ++t;
	lowest[node] = discovery[node];
	s.push(node);
	in_stack[node] = true;
	for (int neigh : adj[node]) {
		if (discovery[neigh] && !in_stack[neigh])
			continue;

		if (!discovery[neigh])
			dfs(neigh, discovery, in_stack, lowest, s, adj, ctcs, t);

		lowest[node] = min(lowest[node], lowest[neigh]);
	}

	if (lowest[node] == discovery[node]) {
		ctcs.push_back(vector<int> {});

		int x;
		do {
			x = s.top();
			ctcs.back().push_back(x);

			s.pop();
			in_stack[x] = false;
		} while (x != node);
	}
}

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

	int n, m;
	cin >> n >> m;

	vector<vector<int>> adj(1 + n, vector<int> ()), ctcs;
	for (int edge = 1, a, b; edge <= m; ++edge) {
		cin >> a >> b;
		adj[a].push_back(b);
	}

	stack <int> s;
	vector<int> discovery(1 + n, 0), lowest(1 + n);
	vector<bool> in_stack(1 + n, false);
	for (int i = 1, t = 0; i <= n; ++i)
		if (!discovery[i])
			dfs(i, discovery, in_stack, lowest, s, adj, ctcs, t);

	cout << ctcs.size() << '\n';
	for (auto ctc : ctcs) {
		for (int x : ctc)
			cout << x << ' ';
		cout << '\n';
	}

	return 0;
}