Cod sursa(job #3214216)

Utilizator MihneaLoxGheorghe Mihnea Florentin MihneaLox Data 13 martie 2024 21:31:58
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMax = 1e5 + 5;

vector<int>G[NMax], GT[NMax], CTC[NMax];
stack<int>S;

int n,NrCtc,beenThere[NMax];

void read();
void solve();
void DFSP(int nod);
void DFSM(int nod);
void print();

int main() {

	read();
	solve();
	print();

	fin.close();
	fout.close();
	return 0;
}

void read() {

	int  m, x, y;
	fin >> n >> m;

	for (int i = 1; i <= m; ++i) {
		fin >> x >> y;
		G[x].push_back(y);
		GT[y].push_back(x);
	}
}

void solve() {

	for (int i = 1; i <= n; ++i)
		if (!beenThere[i])
			DFSP(i);

	while (!S.empty()) {
		int nod = S.top();
		S.pop();

		if (beenThere[nod] == 1) {
			NrCtc++;
			DFSM(nod);
		}
	}
}

void DFSP(int nod) {

	beenThere[nod] = 1;
	for (auto& i : G[nod])
		if (!beenThere[i])
			DFSP(i);
	S.push(nod);
}

void DFSM(int nod) {

	beenThere[nod] = 2;
	CTC[NrCtc].push_back(nod);

	for (auto& i : GT[nod])
		if (beenThere[i] == 1)
			DFSM(i);
}

void print() {

	fout << NrCtc << endl;
	for (int i = 1; i <= NrCtc; ++i) {
		for (auto& j : CTC[i])
			fout << j << ' ';
		fout << endl;
	}
}