Cod sursa(job #2492127)

Utilizator WebDesignbyTMGhiorghiu Ioan-Viorel WebDesignbyTM Data 13 noiembrie 2019 22:51:03
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#define DM 100001
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

ifstream fi ("ctc.in");
ofstream fo ("ctc.out");
int n, m, a, b, idx, cnt;
stack <int> s;
vector <int> ctc[DM];

class Node {
public:
	bool stack;
	int index = -1, low;
	vector <int> edges;

	void addNode(int x) {
		edges.push_back(x);
	}
} v[DM];

void connect_component(int x) {
	v[x].index = v[x].low = ++idx;
	v[x].stack = true;
	s.push(x);
	for (auto i:v[x].edges) {
		if (v[i].index == -1) {
			connect_component(i);
			v[x].low = min(v[i].low, v[x].low);
		}
		else if (v[i].stack)
			v[x].low = min(v[x].low, v[i].index);
	}
	if (v[x].index == v[x].low) {
		do {
			ctc[cnt].push_back(s.top());
			v[s.top()].stack = false;
			s.pop();
		} while (s.top() != x);
		ctc[cnt].push_back(s.top());
		v[s.top()].stack = false;
		s.pop();	
		++cnt;
	}
}

int main() {
	fi >> n >> m;
	for (int i = 1; i <= m; ++i) {
		fi >> a >> b;
		v[a].addNode(b);
	}
	for (int i = 1; i <= n; ++i)
		if (v[i].index == -1)
			connect_component(i);
	fo << cnt << '\n';
	for (int i = 0; i < cnt; ++i)
		for (auto j:ctc[i])
			fo << j << " \n"[j==ctc[i].back()];
	return 0;
}