Cod sursa(job #937492)

Utilizator forgetHow Si Yu forget Data 10 aprilie 2013 14:28:09
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

vector<vector<int> > adjl;
vector<int> index, lowlink;
stack<int> s;
vector<vector<int> > scc;
int mins(0), cur(0);

void strongconnect(int i)
{
	index[i] = lowlink[i] = ++cur;
	s.push(i);
	int v;
	for (vector<int>::iterator it = adjl[i].begin(); it != adjl[i].end(); ++it) {
		v = *it;
		if (index[v] == 0) strongconnect(v);
		if (index[v] > mins && lowlink[i] > lowlink[v]) lowlink[i] = lowlink[v];
	}
	if (index[i] == lowlink[i]) {
		scc.push_back(vector<int>());
		do {
			v = s.top();
			s.pop();
			scc.back().push_back(v);
		} while (v != i);
	}
}

int main() {
	ifstream fin("ctc.in");
	ofstream fout("ctc.out");
	int n, m;
	fin >> n >> m;
	adjl.resize(n+1);
	index.resize(n+1);
	lowlink.resize(n+1);
	int u, v;
	for (; m > 0; --m) {
		fin >> u >> v;
		adjl[u].push_back(v);
	}

	for (int i = 1; i <= n; ++i) {
		if (index[i] == 0) {
			mins = cur;
			strongconnect(i);
		}
	}
	fout << scc.size() << '\n';
	for (int i = scc.size()-1; i >= 0; --i) {
		for (int j = scc[i].size()-1; j >= 0; --j)
			fout << scc[i][j] << ' ';
		fout << '\n';
	}
	return 0;
}