Cod sursa(job #837102)

Utilizator matei_cChristescu Matei matei_c Data 17 decembrie 2012 13:25:32
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

#define maxn 100010
 
int n, m ;
vector <int> graf[maxn], graftr[maxn], sol[maxn] ;
bool sel[maxn] ;
int lista[maxn], nrlista, nrctc ;
 
void df(int nod)
{
    sel[nod] = true ;
 
    for(size_t i = 0; i < graf[nod].size(); ++i )
	{
		int nod_act = graf[nod][i] ; 		
        if( sel[ nod_act ] == false )
            df( nod_act ) ;
	}
	
    lista[ ++nrlista ] = nod;
}
 
void dftrans(int nod)
{
    sel[nod] = true ;
    sol[nrctc].push_back(nod) ;
 
    for(size_t i = 0; i < graftr[nod].size(); ++i )
	{
		int nod_act = graftr[nod][i] ;
        if( sel[ nod_act ] == false )
            dftrans( nod_act ) ;
	}	
}
 
int main()
{
	
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
 
    scanf("%d%d", &n, &m);
	
    for(int i = 1; i <= m; ++i )
    {
		int x, y ;
		scanf("%d%d", &x, &y);
        graf[x].push_back(y) ;
        graftr[y].push_back(x) ;
    }

    for(int i = 1; i <= n; ++i )
        if( sel[i] == false )
            df(i) ;
 
    memset( sel, 0, sizeof(sel) ) ;
	
    for(int i = n; i >= 1; --i )
    {
		if( sel[ lista[i] ] == false )
        {
            ++nrctc ;
            dftrans( lista[i] ) ;
        }
	}	
 
    printf("%d\n", nrctc);
    
	for(int i = 1; i <= nrctc; ++i )
    {
        for(size_t j = 0; j < sol[i].size(); ++j )
            printf("%d ", sol[i][j]);
        printf("\n");
    }
	
    return 0 ;

}