Cod sursa(job #383088)

Utilizator GotenAmza Catalin Goten Data 15 ianuarie 2010 17:12:11
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<fstream.h>

int low[100100],ind[100100],in,st[100100],q,start[100100],v[200100][2],nr,sol[100100],x,y,n,m,i,k,j,h[100100],cont;

int minim(int ee, int ff)
{
	if(ee>ff)
		return ff;
	return ee;
}


void tarjan(int nod)
{
	int t;
	low[nod]=ind[nod]=in;
	in++;
	st[++q]=nod;
	h[nod]=1;
	t=start[nod];
	while(t)
	{
		if(!ind[v[t][0]])
		{
			
			tarjan(v[t][0]);
			low[nod]=minim(low[nod],low[v[t][0]]);
		}
		else
			if(h[v[t][0]]&&v[t][0])
				low[nod]=minim(low[nod],ind[v[t][0]]);
		t=v[t][1];
	}
	if(low[nod]==ind[nod])
	{
		nr++;
		do
		{
			h[st[q]]=0;
			sol[++cont]=st[q];
			q--;
		}
		while(sol[cont]!=nod);
		sol[++cont]=0;
	}
}		

int main()
{
	ifstream f("ctc.in");
	ofstream g("ctc.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		v[++k][0]=y;
		v[k][1]=start[x];
		start[x]=k;
	}
	in=1;
	for(i=1;i<=n;i++)
		if(!ind[i])
			tarjan(i);
	g<<nr<<'\n';
	j=0;
	for(i=1;i<=nr;i++)
	{
		j++;
		while(sol[j])
			g<<sol[j++]<<' ';
		g<<'\n';
	}
	return 0;
}