Cod sursa(job #1366331)

Utilizator ooptNemes Alin oopt Data 28 februarie 2015 22:48:46
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
// ctc
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cstring>

#define NMax 100005
#define pb push_back

using namespace std;

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

int n, m;
vector<int> V[NMax];
int lvl[NMax], best[NMax];
stack<int> q;
vector< vector<int> > sol;
bool instack[NMax];

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

void dfs(int node, int ind) {
	q.push(node);
	instack[node] = true;
	best[node] = lvl[node] = ind+1;

	for (unsigned i=0;i<V[node].size();i++) {
		int vecin = V[node][i];

		if (lvl[vecin] == -1)
			dfs(vecin, lvl[node]);
		best[node] = min(best[node], best[vecin]);
	}

	if (best[node] == lvl[node]) {
		vector<int> add;
		while (1) {
			if (q.empty()) break;

			int ex = q.top();
			q.pop();
			add.pb(ex);
			instack[ex] = false;
		
			if (ex == node)
				break;
		}

		sol.pb(add);
	}
}

void output() {
	g<<sol.size()<<'\n';
	for (unsigned i=0;i<sol.size();i++) {
		for (unsigned j=0;j<sol[i].size();j++)
			g<<sol[i][j]<<' ';
		g<<'\n';
	}
}

int main() {

	memset(lvl, -1, sizeof(lvl));
	read();
	for (int i=1;i<=n;i++)
		if (lvl[i] == -1)
			dfs(i,0);
	output();

	f.close(); g.close();
	return 0;
}