Cod sursa(job #834058)

Utilizator matei_cChristescu Matei matei_c Data 13 decembrie 2012 18:03:48
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std ;

#define maxn 200000

int n, m ;
vector< pair<int, int> > vecini[maxn] ;
bool sel[maxn] ;
bool seltr[maxn] ;
bool elim[maxn] ;
vector<int> sol[maxn] ;
int nrc ;
int nrelim ;

void df_norm(int nod)
{
	sel[nod] = true ;
	
	for(size_t i = 0; i < vecini[nod].size(); ++i )
	{
		int nod_act = vecini[nod][i].first ;
		if( vecini[nod][i].second == 1 && sel[ nod_act ] == false && elim[ nod_act ] == false )
			df_norm( nod_act ) ;
	}	
}

void df_trans(int nod)
{
	seltr[nod] = true ;
	
	for(size_t i = 0; i < vecini[nod].size(); ++i )
	{
		int nod_act = vecini[nod][i].first ;
		if( vecini[nod][i].second == 2 && seltr[ nod_act ] == false && elim[ nod_act ] == false )
			df_trans( 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 a, b ;
		scanf("%d%d", &a, &b);
		vecini[a].push_back( make_pair(b, 1) ) ;
		vecini[b].push_back( make_pair(a, 2) ) ;
	}	
	
	for(int i = 1; i <= n; ++i )
	{
		if( elim[i] == false )
		{	
			df_norm( i ) ;
			df_trans( i ) ;
			
			
			++nrc ;
			
			for(int j = 1; j <= n; ++j )
			{
				if( sel[j] == true && seltr[j] == true )
				{
					sol[nrc].push_back(j) ;
					elim[j] = true ;
					++nrelim ;
				}	
			}
			if( nrelim == n )
				break ;
			
			memset( sel, 0, sizeof(sel) );
			memset( seltr, 0, sizeof(seltr) ) ;
		}
	}
	
	printf("%d\n", nrc);
	
	for(int i = 1; i <= nrc; ++i )
	{	
		for(size_t j = 0; j < sol[i].size(); ++j )
			printf("%d ", sol[i][j]);
		printf("\n");
	}	
		
	return 0 ;
	
}