Cod sursa(job #1584750)

Utilizator AndreiGrigorasAndrei Grigoras AndreiGrigoras Data 30 ianuarie 2016 14:16:30
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <vector>

using namespace std;

ofstream fout ( "ctc.out" ) ;

int n , m , vis[100200] , order[100200] , beg , comp ;
vector<int> G[100200] , GT[100200] , C[100200] ;

void read()
{
    int x , y ;
    freopen ( "ctc.in" , "r" , stdin ) ;
    scanf ( "%d %d" , &n , &m ) ;
    for ( int i = 1 ; i <= m ; i++ )
    {
        scanf ( "%d %d" , &x , &y ) ;
        G[x].push_back(y) ;
        G[y].push_back(x) ;
    }
}

void dfs ( int node )
{
    vis[node] = 1 ;
    for ( vector<int> :: iterator it = G[node].begin() ; it != G[node].end() ; ++it )
        if ( !vis[*it] )
            dfs(*it) ;
    order[++beg] = node ;
}

void dfst ( int node )
{
    vis[node] = 0 ;
    for ( vector<int> :: iterator it = GT[node].begin() ; it != GT[node].end() ; ++it )
        if ( vis[*it] )
            dfst(*it) ;
    C[comp].push_back(node) ;
}

int main()
{
    read() ;
    for ( int i = 1 ; i <= n ; ++i )
        if ( !vis[i] )
            dfs(i) ;
    for ( int i = n ; i >= 1 ; --i )
        if ( vis[order[i]] )
        {
            comp++ ;
            dfst(order[i]) ;
        }
    fout << comp << '\n' ;
    for ( int i = 1 ; i <= comp ; ++i )
    {
        for ( vector<int> :: iterator it = C[i].begin() ; it != C[i].end() ; ++it )
            fout << *it << ' ' ;
        fout << '\n' ;
    }
    return 0;
}