Cod sursa(job #748565)

Utilizator alexdmotocMotoc Alexandru alexdmotoc Data 13 mai 2012 19:44:46
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

#define maxN 100005
#define PB push_back

int N , M , dim , a , b;
bool viz[maxN];

vector <int> lista[maxN] , lista2[maxN] , Q , sol[maxN];

void DFS (int nod)
{
	if (viz[nod])
		return;
	
	viz[nod] = true;
	
	for (unsigned int i = 0 ; i < lista[nod].size () ; ++i)
	{
		int nodcur = lista[nod][i];
		
		if (viz[nodcur])
			continue;
		
		DFS (nodcur);
	}
	
	Q.PB (nod);
}

void DFS2 (int nod)
{
	if (viz[nod])
		return;
	
	viz[nod] = true;
	sol[dim].PB (nod);
	
	for (unsigned int i = 0 ; i < lista2[nod].size () ; ++i)
	{
		int nodcur = lista2[nod][i];
		
		if (viz[nodcur])
			continue;
		
		DFS2 (nodcur);
	}
}

void Korsaju ()
{
	memset (viz , 0 , sizeof (viz));
	
	for (int i = Q.size () - 1 ; i >= 0 ; --i)
	{
		if (viz[Q[i]])
			continue;
		
		++dim;
		DFS2 (Q[i]);
	}
}

int main ()
{
	freopen ("ctc.in" , "r" , stdin);
	freopen ("ctc.out" , "w" , stdout);
	
	scanf ("%d %d" , &N , &M);
	
	while (M --)
	{
		scanf ("%d %d" , &a , &b);
		
		lista[a].PB (b);
		lista2[b].PB (a); 
	}
	
	for (int i = 1 ; i <= N  ; ++i)
	{
		if (viz[i])
			continue;
		
		DFS (i);
	}
	
	Korsaju ();
	
	printf ("%d\n" , dim);
	
	for (int i = 1 ; i <= dim ; ++i)
	{
		for (unsigned int j = 0 ; j < sol[i].size () ; ++j)
			printf ("%d " , sol[i][j]);
		
		printf ("\n");
	}
	
	return 0;
}