Cod sursa(job #3370806)

Utilizator lefterache_stefanLefterache Stefan lefterache_stefan Data 27 octombrie 2026 12:22:10
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int MAXIM = 100005;
int n, m;

vector<int> graf[MAXIM];
vector<int> graf_transpus[MAXIM];
vector<int> componente[MAXIM];

bool vizitat[MAXIM];
int finalizare[MAXIM];
int index_finalizare = -1;
int nr_componente = 0;

static inline void citire() {
	fin >> n >> m;

	for (int i = 0; i < m; i++) {
		int x, y;
		fin >> x >> y;
		graf[x].push_back(y);
		graf_transpus[y].push_back(x);
	}
}

static void dfs(int nod) {
	vizitat[nod] = true;

	for (auto vecin : graf[nod]) {
		if (vizitat[vecin]) {
			continue;
		}
		dfs(vecin);
	}

	finalizare[++index_finalizare] = nod;
}

static void dfs_invers(int nod) {
	vizitat[nod] = true;
	componente[nr_componente].push_back(nod);

	for (auto vecin : graf_transpus[nod]) {
		if (vizitat[vecin]) {
			continue;
		}
		dfs_invers(vecin);
	}
}

static inline void rezolvare() {
	for (int nod = 1; nod <= n; nod++) {
		if (!vizitat[nod]) {
			dfs(nod);
		}
	}

	fill(vizitat, vizitat + n + 1, false);

	for (int i = index_finalizare; i >= 0; i--) {
		int nod = finalizare[i];

		if (vizitat[nod]) {
			continue;
		}

		nr_componente++;
		dfs_invers(nod);
	}
}

static inline void afisare() {
	fout << nr_componente << '\n';

	for (int i = 1; i <= nr_componente; i++) {
		for (auto nod : componente[i]) {
			fout << nod << ' ';
		}
		fout << '\n';
	}
}

int main() {
	citire();
	rezolvare();
	afisare();
}