Cod sursa(job #651336)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 20 decembrie 2011 08:34:25
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int dim = 200005;
vector <int> C[dim], V[dim];
int N, M, NC, S[dim], niv[dim], low[dim], viz[dim];

void cit ()
{
	fi >> N >> M;
	for (int i = 1, x, y; i <= M; i++)
	{
		fi >> x >> y;
		V[x].push_back (y);
	}	
}

void dfs (int n, int t)
{
	niv[n] = low[n] = niv[t] + 1;
	viz[n] = 1;
	S[++S[0]] = n;
	
	for (int i = 0, f; i < V[n].size(); i++)
	{
		f = V[n][i];
		if (niv[f] == 0)
		{
			dfs (f, n);
			low[n] = min (low[f], low[n]);
		} 
		else if (viz[f] == 1)
		{
			low[n] = min (low[f], low[n]);
		}		
	}
	
	if (niv[n] == low[n])
	{
		NC++;
		while (S[S[0] + 1] != n)
		{
			viz[S[S[0]]] = 0;
			C[NC].push_back (S[S[0]]);
			S[0]--;
		}		
	}
}

void afi ()
{
	fo << NC << '\n';
	for (int i = 1; i <= NC; i++)
	{
		for (int j = 0; j < C[i].size(); j++)
			fo << C[i][j] << ' ';
		fo << '\n';
	}	
}

int main ()
{
	cit ();
	for (int i = 1; i <= N; i++)
		if (niv[i] == 0)
			dfs (i, 0);
	afi ();
	return 0;
}