Cod sursa(job #362424)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 9 noiembrie 2009 18:04:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<cstdio>
#include<iterator>
#include<vector>
#include<stack>
using namespace std;
#define N 100005
#define pb push_back
#define p push
vector<int>a[N],indx,llink,cod;
vector<bool>este;
stack<int>s;
vector< vector<int> > rez;
#define Min(a,b) ((a)<(b)?(a):(b))
int ind,n,m;
void citire()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	scanf("%d%d",&n,&m);
	indx.resize(n);
	indx.assign(n,-1);
	este.resize(n);
	este.assign(n,false);
	llink.resize(n);
	int x,y;
	for (int i=0; i<m; ++i)
	{
		scanf("%d%d",&x,&y);
		a[x-1].pb(y-1);
	}
	
}
void alg_tarjan(int n)
{
	llink[n]=indx[n]=ind;
	++ind;
	s.p(n),este[n]=true;
	vector<int>::const_iterator g=a[n].end();
	for (vector<int>::const_iterator it=a[n].begin();it!=g; ++it)
	{
		if (indx[*it]==-1)
		{
			alg_tarjan(*it);
			llink[n]=Min(llink[n],llink[*it]);
		}
		else
			if (este[*it])
			{
				llink[n]=Min(llink[n],llink[*it]);
			}
	}
	if (indx[n]==llink[n])
	{
		cod.clear();
		int nod;
		do
		{
			nod=s.top();
			cod.pb(nod);
			s.pop(),este[nod]=false;
		}
		while (nod!=n);
		rez.pb(cod);
	}
}
void componente()
{
	for (int i=0; i<n; ++i)
	{
		if (indx[i]==-1)
			alg_tarjan(i);
	}
}
void afis()
{
	size_t g=rez.size();
	printf("%d\n",g);
	for (size_t i=0; i<g; ++i)
	{
		size_t g1=rez[i].size();
		for (size_t j=0; j<g1; ++j)
			printf("%d ",rez[i][j]+1);
		printf("\n");
	}
}
int main()
{
	citire();
	componente();
	afis();
}