Cod sursa(job #3125180)

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

using namespace std;

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

vector<int> graf[100005];
vector<int> grafinv[100005];
vector<int> s;
bool v[100005];
int v2[100005];
int id = 0;

void dfs(int now) {
	v[now] = true;
	for (int i : graf[now]) {
		if (!v[i]) {
			dfs(i);
		}
	}
	s.push_back(now);
}

void dfs2(int now) {
	v2[now] = id;
	for (int i : grafinv[now]) {
		if (!v2[i]) {
			dfs2(i);
		}
	}
}

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);
		grafinv[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) {
		if (v[i]) continue;
		dfs(i);
	}
	for (int i = s.size() - 1; i >= 0; i--) {
		if (v2[s[i]] != 0) continue;
		id++;
		dfs2(s[i]);
	}
	vector<pair<int, int>> noduri;
	for (int i = 1; i <= n; i++) {
		noduri.push_back({ v2[i], i });
	}
	sort(noduri.begin(), noduri.end());
	cout << id << '\n';
	for (int i = 0; i < noduri.size(); i++) {
		cout << noduri[i].second << ' ';
		if (i + 1 < noduri.size() && noduri[i].first != noduri[i + 1].first) {
			cout << '\n';
		}
	}
	return 0;
}