Cod sursa(job #1281507)

Utilizator gerd13David Gergely gerd13 Data 3 decembrie 2014 11:38:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <list>
#include <set>
#include <stack>

/////////////////////////////////////////

using namespace std ;

/////////////////////////////////////////

const int NMAX = 200005 ;
const int INF = 0x3f3f3f3f ;

////////////////////////////////////////

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

///////////////////////////////////////


void READ() ;
void Kosaraju() ;
void PRINT() ;

///////////////////////////////////

int N, M, cnt ;

vector <int> G[NMAX], T[NMAX], SOL[NMAX] ;
stack <int> ls ;
bool use[NMAX] ;

////////////////////////////////////////

static inline int min(int a, int b) {return (a < b ? a : b);}
static inline int max(int a, int b) {return (a > b ? a : b);}

///////////////////////////////////////

 inline void READ()
{
	fin >> N >> M ;

	while(M -- )
	{
		int x,  y ;

		fin >> x >> y ;

		G[x].push_back(y) ;
		T[y].push_back(x) ;

	}
}

////////////////////////////////////////

void DFS(int node)
{
	use[node]  = true ;

	for(auto i : G[node])
		if(!use[i])
			DFS(i) ;
	ls.push(node) ;

}

///////////////////////////

void TransDFS(int node)
{
	use[node] = false ;
	SOL[cnt].push_back(node) ;
	for(auto i : T[node])
		if(use[i])
			TransDFS(i) ;
}

//////////////////////////

 inline void Kosaraju()
{
	for(int i = 1 ; i <= N ; ++ i )
		if(!use[i])
			DFS(i) ;

		while(!ls.empty())
		{
			if(use[ls.top()])
			{
				++ cnt ;
				TransDFS(ls.top()) ;
			}

		ls.pop() ;

		}


}

////////////////////////
 inline void PRINT()
{
	fout << cnt << '\n' ;

	for(int i = 1 ; i <= cnt ; ++ i)
		{for(auto node : SOL[i])
			fout << node << ' ' ;
			fout << '\n' ;
		}


}

///////////////////////////////////////////////

int main()
{
	READ() ;
	Kosaraju() ;
	PRINT() ;


	fin.close() ;
	fout.close() ;
	return  0 ;
}