Cod sursa(job #2120953)

Utilizator k.bruenDan Cojocaru k.bruen Data 3 februarie 2018 10:16:10
Problema Componente tare conexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>

std::ifstream in("ctc.in");
std::ofstream out("ctc.out");

const int MAX = 100000;

std::vector<int> Graf[MAX];
std::stack<int> Stack;
int index[MAX];
int lowlink[MAX];
std::bitset<MAX> instack;

int _index = 1;
int _results = 0;

std::vector< std::vector<int> > results;

void strongconnect(int v) {
	index[v] = lowlink[v] = _index++;
	Stack.push(v);
	instack[v] = true;

	for (int w : Graf[v]) {
		if (index[w] == 0) {
			strongconnect(w);
			lowlink[v] = (lowlink[w] > lowlink[v]) ? lowlink[v] : lowlink[w];
		}
		else if (instack[w]) {
			lowlink[v] = (index[w] > lowlink[v]) ? lowlink[v] : index[w];
		}
	}

	if (lowlink[v] == index[v]) {
		int w;
		std::vector<int> result;
		do {
			w = Stack.top(); Stack.pop();
			instack[w] = false;

			result.push_back(w);
		} while (w != v);

		if (result.size() == 1 && result[0] == 0);
		else {
			_results++;
			results.push_back(result);
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);

	int n, m;
	in >> n >> m;
	for (int i = 0; i < m; ++i) {
		int x, y;
		in >> x >> y;
		Graf[x].push_back(y);
	}

	for (int i = 0; i < n; ++i) {
		if (index[i] == 0) {
			strongconnect(i);
		}
	}

	out << _results << '\n';
	for (std::vector<int> r : results) {
		for (int val : r) {
			out << val << ' ';
		}
		out << '\n';
	}

	return 0;
}