Cod sursa(job #1179144)

Utilizator vld7Campeanu Vlad vld7 Data 28 aprilie 2014 02:56:12
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

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

const int MAX_N = 100005;
const int MAX_M = 200005;

int n, m;
int idx[MAX_N];			// indicele in parcurgere
int lowlink[MAX_N];		// cat de sus pot sa ma duc
int index;

bool inStack[MAX_N];
bool used[MAX_N];

vector <int> L[MAX_N], Temp[MAX_N];
vector <vector <int> > Ans, Ans2;
stack <int> Stack;

void init() {
	for (int i = 0; i < MAX_N; i++)
		idx[i] = -1;
}

void read() {
	f >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b;
		f >> a >> b;
		L[a].push_back (b);
	}
}

void tarjan (int nod) {
	index++;
	idx[nod] = index;
	lowlink[nod] = index;
	Stack.push (nod);
	inStack[nod] = true;
	
	for (vector <int> :: iterator it = L[nod].begin(); it != L[nod].end(); ++it)
		if (idx[*it] == -1) {
			tarjan (*it);
			lowlink[nod] = min (lowlink[nod], lowlink[*it]);
		} else if (inStack[*it]) {
			lowlink[nod] = min (lowlink[nod], lowlink[*it]);
		}
		
	// daca e radacina componentei tare conexe
	if (lowlink[nod] == idx[nod]) {
		vector <int> Temp;
		int temp_node;
		
		do {
			temp_node = Stack.top();
			Temp.push_back (temp_node);
			Stack.pop();
			inStack[temp_node] = false;
		} while (temp_node != nod);
		
		Ans.push_back (Temp);
	}
}

void write() {
	g << Ans2.size() << '\n';
	for (int i = 0; i < (int)Ans2.size(); i++) {
		for (vector <int> :: iterator it = Ans2[i].begin(); it != Ans2[i].end(); ++it)
			g << *it << " ";
		g << '\n';
	}
}

int main() {
	init();
	read();
	
	for (int i = 1; i <= n; i++)
		if (idx[i] == -1)
			tarjan (i);
		
	for (int i = 1; i <= n; i++)
		Temp[lowlink[i]].push_back (i);
	
	for (int i = 1; i <= n; i++)
		if (!used[lowlink[i]]) {
			used[lowlink[i]] = 1;
			Ans2.push_back (Temp[lowlink[i]]);
		}
		
	write();
		
	return 0;
}