Cod sursa(job #1106390)

Utilizator span7aRazvan span7a Data 12 februarie 2014 19:33:58
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
struct nod
{
	int inf;
	nod* leg;
};
typedef nod* PNod;
PNod G[100001],Gt[100001],sol[100005];
int viz1[100001],stiv[100001],n,m,t,nrc;
void add1(int x,int y)
{
	PNod p=new nod;
	p->inf=y;
	p->leg=G[x];
	G[x]=p;
}
void add2(int x,int y)
{
	PNod p=new nod;
	p->inf=y;
	p->leg=Gt[x];
	Gt[x]=p;
}
void add3(int x,int y)
{
	PNod p=new nod;
	p->inf=y;
	p->leg=sol[x];
	sol[x]=p;
}
void df1(int i)
{
	PNod p;
	viz1[i]=1;

	for( p=G[i];p;p=p->leg)
		if(viz1[p->inf]==0)
			df1(p->inf);
	t++;
	stiv[t]=i;
	
}
void df2(int i,int poz)
{
	viz1[i]=1;
	add3(poz,i);
	for(PNod p=Gt[i];p;p=p->leg)
		if(viz1[p->inf]==0)
		{	
			df2(p->inf,poz);
		}
}
void ccon()
{
	int i;
	for(i=n;i>=1;i--)
	{
		if(viz1[i]==0)
			{df1(i);}
	}
	for(i=1;i<=n;i++)
		viz1[i]=0;
	for(i=n;i>=1;i--)
	{
				if(viz1[stiv[i]]==0)
				{
					nrc++;
					df2(stiv[i],nrc);
					
				}
		
	}
	g<<nrc<<'\n';
	for(i=1;i<=nrc;i++)
	{
		for(PNod p=sol[i];p;p=p->leg)
			g<<p->inf<<" ";
		g<<'\n';
	}
		
}
int main()
{
	int i,x,y;
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		add1(x,y);
		add2(y,x);
	}
	ccon();
	return 0;
}