Pagini recente » Cod sursa (job #1087811) | Cod sursa (job #1723716) | Cod sursa (job #2773549) | Cod sursa (job #3139090) | Cod sursa (job #1281509)
#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 ;
}