Cod sursa(job #2984521)

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

using namespace std;

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

const int NMax = 100005;
vector<int> v[NMax],c[NMax],con;
bool instiva[NMax];
int lowlink[NMax], idx[NMax],com[NMax];
int n, m,indecs,nrctc;
stack<int> s;
void tarjan(int nod) {
	idx[nod] = lowlink[nod] = indecs;
	indecs++;
	s.push(nod);
	instiva[nod] = true;
	for (unsigned i = 0; i < v[nod].size(); i++) {
		int vecin = v[nod][i];
		if (idx[vecin] == -1) {
			tarjan(vecin);
			lowlink[nod] = min(lowlink[nod], lowlink[vecin]);
		}
		else {
			if (instiva[vecin]) {
				lowlink[nod] = min(lowlink[nod], lowlink[vecin]);
			}
		}

	}
	if (idx[nod] == lowlink[nod]) {
		nrctc++;
		int newnod;
		do {
			newnod = s.top();
			c[nrctc].push_back(newnod);
			s.pop();
			instiva[newnod] = false;
		} while (newnod != nod);
	}
}
int main() {
	f>> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		f >> x >> y;
		v[x].push_back(y);
	}
	for (int i = 1; i <= n; i++) {
		idx[i] = -1;
	}
	for (int i = 1; i <= n; i++) {
		if (idx[i] == -1) {
			tarjan(i);
		}
	}
	g << nrctc<<'\n';
	for (int i = nrctc; i >= 1;--i) {
		for (unsigned j = 0; j < c[i].size(); j++) {
			g << c[i][j] << ' ';
		}
		g << '\n';
	}
}