Cod sursa(job #819694)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 19 noiembrie 2012 16:37:06
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <stack>
using namespace std;

ifstream fi ("ctc.in");
ofstream fo ("ctc.out");

const int dim = 100005;
int N, niv[dim], low[dim];
vector <int> V[dim], r;
stack <int> S;
vector <vector <int> > R;

void cit ()
{
	int x, y, m;
	fi >> N >> m;
	while ( m -- )
	{
		fi >> x >> y;
		V[x].push_back (y);
	}
}

void dfs (int n)
{
	int f;
	low[n] = niv[n] = ++niv[0];
	S.push (n);
	
	for (int i = 0; i < V[n].size(); i++)
	{
		f = V[n][i];
		if (niv[f] == 0)
		{
			dfs (f);
			low[n] = min (low[n], low[f]);
		}
		else if (niv[f] != -1)
		{
			low[n] = min (low[n], niv[f]);
		}
	}
	
	if (niv[n] == low[n])
	{
		while (!r.empty())
			r.pop_back ();
		do {
			f = S.top ();
			S.pop ();
			r.push_back (f);
			niv[f] = -1;
		} while (f != n);
		R.push_back (r);
	}
}

void rez ()
{
	int i, j;
	for (i = 1; i <= N; i++)
		if (niv[i] == 0)
			dfs (i);
	fo << R.size () << '\n';
	for (i = 0; i < R.size(); i++)
	{
		for (j = 0; j < R[i].size (); j++)
			fo << R[i][j] << ' ';
		fo << '\n';
	}
}

int main ()
{
	cit ();
	rez ();
	return 0;
}