Cod sursa(job #3332140)

Utilizator misterperdymatei alexandru antonie misterperdy Data 4 ianuarie 2026 16:54:21
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;

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

//determinare nr componente tare conexe

vector<vector<int>> vecini;
vector<vector<int>> tVecini;
vector<bool> vizitat;
stack<int> stiva;

//DFS intial sa creem stiva pt kosaraju
void DFS_1(int nod_curent) {
	//cout << nod_curent << ' ';
	vizitat[nod_curent] = true;

	for (auto v : vecini[nod_curent]) {
		if (!vizitat[v]) {
			DFS_1(v);
		}
	}

	//am terminat de procesat toti vecinii -> bagam in stiva
	stiva.push(nod_curent);
}

//DFS pe transpus
void DFS_2(int nod_curent, vector<int>& componentaConexa) {
	//cout << nod_curent << ' ';
	vizitat[nod_curent] = true;

	componentaConexa.push_back(nod_curent);
	
	for (auto v : tVecini[nod_curent]) {
		if (!vizitat[v]) {
			DFS_2(v, componentaConexa);
		}
	}
}

int main() {
	int n, m;

	vector<int> componentaConexa;
	vector<vector<int>> componenteConexe;

	fin >> n >> m;

	vecini.resize(n + 1);
	vizitat.resize(n + 1);
	vizitat.assign(n+1  , false);
	tVecini.resize(n + 1);

	for (int i = 1; i <= m; i++) {
		int x, y;
		fin >> x >> y;

		vecini[x].push_back(y);
		tVecini[y].push_back(x);
		
	}

	for (int i = 1; i <= n; i++) {
		//DFS pe fiecare nod nevizitat
		if (!vizitat[i]) {
			DFS_1(i);
		}
	}

	//resetam vizitat 
	vizitat.assign(n + 1, false);

	int nr_componente = 0;

	//facem DFS pe fiecare nod nevizitat din stiva pe graful transpus , nr de DFS uri e nr de componente conexe
	while (!stiva.empty()) {
		//scoatem din stiva
		int nod_curent = stiva.top();
		stiva.pop();

		componentaConexa.clear();

		//daca e nevizitat, DFS
		if (!vizitat[nod_curent]) {
			DFS_2(nod_curent, componentaConexa);
			nr_componente++;
		}


		if (!componentaConexa.empty()) {
			componenteConexe.push_back(componentaConexa);
		}
	}


	fout << nr_componente;
	
	for (auto c : componenteConexe) {
		fout << endl;
		sort(c.begin(), c.end());
		for (auto c2 : c) {
			fout << c2 << ' ';
		}
	}
	return 0;
}