Cod sursa(job #2081612)

Utilizator ice_creamIce Cream ice_cream Data 4 decembrie 2017 21:26:00
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 100000 + 1;

int n;
int ind;
bool in_stack[NMAX];
int index_nod[NMAX];
int lowlink[NMAX];
vector <int> graf[NMAX];
stack <int> st;

vector < vector <int> > sol;

void citeste() {
	int m, a, b;
	f >> n >> m;
	while (m--) {
		f >> a >> b;
		graf[a].push_back(b);
	}
}

int ctc(int nod) {
	if (index_nod[nod]) return index_nod[nod];

	index_nod[nod] = ++ind;
	lowlink[nod] = ind;
	st.push(nod);
	in_stack[nod] = true;
 

	int lowlink_crt = ind;

	int l = graf[nod].size();
	for (int i = 0; i < l; i++) {
		int fiu = graf[nod][i];
		int lowlink_fiu = ctc(fiu);
		if (!in_stack[fiu]) continue;
		lowlink_crt = min(lowlink_crt, lowlink_fiu);
	}
	lowlink[nod] = lowlink_crt;
	if (lowlink[nod] != index_nod[nod]) return lowlink[nod];

	vector <int> comp_crt;
	int top;
	do {
		top = st.top();
		st.pop();
		in_stack[top] = false;
		comp_crt.push_back(top);
	} while(top != nod);

	sol.push_back(comp_crt);
	return lowlink[nod];
}

void rezolva() {
	for (int i = 1; i <= n; i++)
		if (!index_nod[i]) ctc(i);
}

void scrie() {
	int l = sol.size();
	g << l << '\n';
	for (int i = 0; i < l; i++) {
		int k = sol[i].size();
		for (int j = 0; j < k; j++) {
			g << sol[i][j] << ' ';
		}
		g << '\n';
	}
}

int main() {
	citeste();
	rezolva();
	scrie();
	return 0;
}