Cod sursa(job #2984480)

Utilizator RobyDarioCorjuc Roberto RobyDario Data 24 februarie 2023 11:56:38
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>


using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

const int NMax = 100005;
stack<int> s;
vector<int> gi[NMax], gt[NMax], ctc[NMax];
int n,vizitat[NMax],nrctc,m;

void dfs(int nod) {
	vizitat[nod] = 1;
	for (unsigned i = 0; i < gi[nod].size(); i++) {
		int vecin = gi[nod][i];
		if (!vizitat[vecin])
			dfs(vecin);
	}
	s.push(nod);
}
void dfs_t(int nod) {
	vizitat[nod] = 2;
	ctc[nrctc].push_back(nod);
	for (unsigned i = 0; i < gt[nod].size(); i++) {
		int vecin = gt[nod][i];
		if (vizitat[vecin] == 1) {
			dfs_t(vecin);
		}
	}
}
void solve() {
	for (int i = 1; i <= n; i++) {
		if (!vizitat[i]) {
			dfs(i);
		}
	}
	while (!s.empty()) {
		int nod = s.top();
		if (vizitat[nod] == 1) {
			nrctc++;
			dfs_t(nod);
		}
		s.pop();
	}
}
int main(){
	f >> n>> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		f >> x >> y;
		gi[x].push_back(y);
		gt[y].push_back(x);
	}
	solve();
	g << nrctc << '\n';
	for (int i = 1; i <= nrctc; i++) {
		for (unsigned j = 0; j < ctc[i].size(); j++) {
			g<< ctc[i][j] << ' ';
		}
		g<< '\n';
	}
}