Cod sursa(job #3125184)

Utilizator game_difficultyCalin Crangus game_difficulty Data 2 mai 2023 10:49:06
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

vector<int> graf[100005];
vector<int> nn;
int v[100005];
int bestsus[100005];
bool v2[100005];
vector<int> cc[100005];
int nrcc = 0;

void dfs(int now, int prev = 0) {
	v[now] = prev + 1;
	nn.push_back(now);
	v2[now] = true;
	bestsus[now] = v[now];
	for (int i : graf[now]) {
		if (!v[i]) {
			dfs(i, v[now]);
		}
		if (v2[i]) {
			bestsus[now] = min(bestsus[now], bestsus[i]);
		}
	}
	if (bestsus[now] == v[now]) {
		nrcc++;
		while (nn.back() != now) {
			cc[nrcc].push_back(nn.back());
			v2[nn.back()] = false;
			nn.pop_back();
		}
		cc[nrcc].push_back(nn.back());
		v2[nn.back()] = false;
		nn.pop_back();
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		graf[x].push_back(y);
	}
	for (int i = 1; i <= n; i++) {
		if (v[i]) continue;
		dfs(i);
	}
	cout << nrcc << '\n';
	for (int i = 1; i <= nrcc; i++) {
		for (int j = 0; j < cc[i].size(); j++) {
			cout << cc[i][j] << ' ';
		}
		cout << '\n';
	}
	return 0;
}