Cod sursa(job #483065)

Utilizator mottyMatei-Dan Epure motty Data 6 septembrie 2010 19:47:55
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
//CTC
#include<cstdio>
#include<vector>

using namespace std;

const int N=100001;

int n, m, rep[N], poz, nrcc;

bool viz[N];

vector <int> g[N];
vector <int> rv[N];
vector <int> ctc[N];

void Read()
{
	int a, b;
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%d%d",&a,&b);
		g[a].push_back(b);
		rv[b].push_back(a);
	}
}

void Sat(int i)
{
	int sz=g[i].size();
	viz[i]=1;
	
	for( int j=0; j<sz; ++j)
		if(!viz[g[i][j]])
			Sat(g[i][j]);
	
	rep[++poz]=i;
}

void Parc()
{
	for( int i=1; i<=n; ++i)
		if(!viz[i])
			Sat(i);
}

void Rsat( int i, int cc)
{
	int sz=rv[i].size();
	viz[i]=0;
	ctc[cc].push_back(i);
	
	for( int j=0; j<sz; ++j)
		if(viz[rv[i][j]])
			Rsat( rv[i][j], cc);
}

void InvP()
{
	for( int i=n; i>=1; --i)
		if(viz[rep[i]])
			Rsat( rep[i], ++nrcc);
}

void GetC()
{
	int sz;
	printf("%d\n",nrcc);
	
	for( int i=1; i<=nrcc; ++i)
	{
		sz=ctc[i].size();
		for( int j=0; j<sz; ++j)
			printf("%d ",ctc[i][j]);
		printf("\n");
	}
}

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	
	Read();
	Parc();
	InvP();
	GetC();
	
	return 0;
}