Cod sursa(job #702422)

Utilizator Catah15Catalin Haidau Catah15 Data 1 martie 2012 21:43:52
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

#define maxN 100010
#define PB push_back

bool viz[maxN];
vector <int> lista[maxN], lista2[maxN], Q;
vector <int> sol[maxN];
bool First_DF = true;
int N, comp;


void DFP (int nod)
{
	viz[nod] = true;

	for (unsigned int i = 0; i < lista[nod].size(); ++ i)
	{
		int nod2 = lista[nod][i];
		
		if (viz[nod2]) continue;
		
		DFP (nod2);
	}
	
	Q.PB (nod);
}


void DFM (int nod)
{
	viz[nod] = true;
	
	sol[comp].PB (nod);
	
	for (unsigned int i = 0; i < lista2[nod].size(); ++ i)
	{
		int nod2 = lista2[nod][i];
		
		if (viz[nod2]) continue;
		
		DFM (nod2);
	}
}


void Kosaraju ()
{
	for (int i = 1; i <= N; ++ i)
	{
		if (viz[i]) continue;
		DFP (i);
	}
	
	memset (viz, false, sizeof (viz));
	
	for (int i = Q.size() - 1; i >= 0; -- i)
	{
		int nod = Q[i];
		
		if (viz[nod]) continue;
		
		++ comp;
		DFM (nod);
	}
}


int main()
{
	freopen ("ctc.in", "r", stdin);
	freopen ("ctc.out", "w", stdout);
	
	int M;
	
	scanf ("%d %d", &N, &M);
	
	while (M --)
	{
		int x, y;
		
		scanf ("%d %d", &x, &y);
		
		lista[x].PB (y);
		lista2[y].PB (x);
	}
	
	Kosaraju ();
	
	printf ("%d\n", comp);
	for (int i = 1; i <= comp; ++ i)
	{
		for (unsigned int j = 0; j < sol[i].size(); ++ j) printf ("%d ", sol[i][j]);
		printf ("\n");
	}
	
	return 0;
}