Cod sursa(job #2984468)

Utilizator RobyDarioCorjuc Roberto RobyDario Data 24 februarie 2023 11:29:11
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 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] != 1)
			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(vecin);
			}
	}
}
void solve() {
	for (int i = 1; i <= n; i++) {
		if (!vizitat[i])
			dfs(i);
	}
	while (!s.empty()) {
		int nod = s.top();
		s.pop();
		if (vizitat[nod] == 1) {
			nrctc++;
			dfs_t(nod);
		}
	}
}
int main() {
	f >> n>>m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		f >> x >> y;
		gi[x].push_back(x);
		gt[y].push_back(y);
	}
	solve();
	g << nrctc << '\n';
	for (int i = 1; i <= nrctc; i++) {
		for (unsigned j = 0; j < gt[nrctc].size(); j++) {
			g<< gt[nrctc][j] << ' ';
		}
		g << '\n';
	}
}