Cod sursa(job #2541749)

Utilizator WebDesignbyTMGhiorghiu Ioan-Viorel WebDesignbyTM Data 8 februarie 2020 20:31:55
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#define DM 100001
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

ifstream fi ("ctc.in");
ofstream fo ("ctc.out");
bool ins[DM];
int n, m, idx[DM], midx[DM], nodes, total, a, b;
stack <int> st;
vector <int> v[DM], ctc[DM];

void discover(int node) {
	idx[node] = midx[node] = ++nodes;
	ins[node] = true;
	st.push(node);
	for (auto i:v[node]) {
		if (!idx[i]) {
			discover(i);
			midx[node] = min(midx[node], midx[i]);
		} else if (ins[i]) {
			midx[node] = min(midx[node], idx[i]);
		}
	}
	if (idx[node] == midx[node]) {
		while (1) {
			a = st.top();
			st.pop();
			ctc[total].push_back(a);
			ins[a] = false;
			if (a == node)
				break;
		}
		++total;
	}
}

int main() {
	fi >> n >> m;
	for (int i = 1; i <= m; ++i) {
		fi >> a >> b;
		v[a].push_back(b);
	}
	for (int i = 1; i <= n; ++i)
		if (!idx[i]) 
			discover(i);
	fo << total << '\n';
	for (int i = 0; i < total; ++i)
		for (auto j:ctc[i])
			fo << j << " \n"[j==ctc[i].back()];
	return 0;
}