Cod sursa(job #535539)

Utilizator david_raucaRauca Ioan David david_rauca Data 17 februarie 2011 13:42:49
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include<fstream>
#include<vector>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

vector<int> st;
bool s[100001];
bool s1[100001];

int n, m, nr, p;

vector<vector<int> > G;
vector<vector<int> > T;
vector<vector<int> > sol;

void Read();
void Solve();
void DF( int x );
void DFT( int x );

int main()
{
	Read();
	Solve();
	
	fin.close();
	fout.close();
	
	return 0;
}

void Read()
{
	fin >> n >> m;
	
	G.resize(n+1);
	T.resize(n+1);
	st.resize(n+1);
	sol.resize(n+1);
	int x, y;
	while( fin >> x >> y )
	{
		G[x].push_back(y);
		T[y].push_back(x);
	}
	/*
	for( int i = 1; i <= n; ++i )
	{
		fout << i <<": ";
		for( int j = 0; j < G[i].size(); ++j )
			fout << G[i][j] << ' ';
		fout << '\n';
	}
	*/
}

void Solve()
{
	nr = 0;
	p = 0;
	for( int i = 1; i <= n; ++i )
		if( !s[i] )
		{
			DF(i);
			st[++p] = i;
		}
	
	for( int i = n; i > 0; --i )
		if( !s1[ st[i] ] )
		{
			nr++;
			DFT( st[i] );
		}
	/*
	for( int i = n; i > 0; --i )
		fout << st[i] << ' ';
	*/
	fout << nr << '\n';
		
	for( int i = 1; i <= nr; ++i )
	{
		for( int j = 0; j < sol[i].size(); ++j )
			fout << sol[i][j] << ' ';
		fout << '\n';
	}
}

void DF( int x )
{
	s[x] = true;
	for( int i = 0; i < G[x].size(); ++i )
		if( !s[ G[x][i] ] )
		{
			DF( G[x][i] );
			st[++p] = G[x][i];
		}
}

void DFT( int x )
{
	s1[x] = true;
	sol[nr].push_back( x );
	for( int i = 0; i < T[x].size(); ++i )
		if( !s1[ T[x][i] ] )
		{
			//sol[nr].push_back( T[x][i] );
			DFT( T[x][i] );
		}
}