Cod sursa(job #236181)

Utilizator blasterzMircea Dima blasterz Data 26 decembrie 2008 21:18:46
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
// componente tare conexe O(n+m)
using namespace std;
#include <string>
#include <cstdio>
#include <vector>
#define N 100001
#define dim 8192

char ax[dim];
int pz;

inline void cit(int &x)
{
	x=0;
	while(ax[pz]<'0' || ax[pz]>'9')
		if(++pz==dim)fread(ax,1,dim,stdin),pz=0;
	while(ax[pz]>='0' && ax[pz]<='9')
	{
		x=x*10+ax[pz]-'0';
		if(++pz==dim)fread(ax,1,dim,stdin),pz=0;
	}
}

struct nod { int x; nod *n;};

nod *a[N];
nod *Ta[N];
int n,m;
int st[N];
int ns;
bool use[N];
vector<vector<int> > sol;

inline void add(int i, int j)
{
	nod *p=new nod;
	p->x=j;
	p->n=a[i];
	a[i]=p;
}

inline void add2(int i, int j)
{
	nod *p=new nod;
	p->x=j;
	p->n=Ta[i];
	Ta[i]=p;
}

void read()
{
	freopen("ctc.out","w",stdout);
	freopen("ctc.in","r",stdin);
	cit(n);cit(m);
	int p,q;
	while(m--)
	{
		cit(p);cit(q);
		add(p,q);
		add2(q,p);
	}
	
}

inline void dfs(int n)
{
	use[n]=1;
	
	for(nod *i=a[n]; i; i=i->n)
		if(!use[i->x])
			dfs(i->x);
	st[++ns]=n;
}

inline void df(int n) // merg pe graful transpus
{
	use[n]=0;
	
	sol[sol.size()-1].push_back(n);
	//printf("%d ", n);
	for(nod *i=Ta[n]; i; i=i->n)
		if(use[i->x])
			df(i->x);
}


void solve()
{
	int i;
	
	for(i=1;i<=n;++i)
		if(!use[i]) dfs(i);
	
	vector<int>aux;
	
	for(i=n; i  ;--i)
		if(use[st[i]])
		{	
			sol.push_back(aux);
			df(st[i]);
		}

	printf("%d\n", sol.size());
	for(i=0;i<sol.size();++i)
	{
		for(int j=0;j<sol[i].size();++j)printf("%d ", sol[i][j]);
		printf("\n");
	}
	
}

int main()
{
	read();
	solve();
	
	return 0;
}