Cod sursa(job #1281509)

Utilizator gerd13David Gergely gerd13 Data 3 decembrie 2014 11:38:53
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 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 ;
}