Cod sursa(job #299735)

Utilizator AndreyPAndrei Poenaru AndreyP Data 6 aprilie 2009 22:38:10
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<stdio.h>
#include<vector>
#include<stack>
#include<bitset>
#include<algorithm>
using namespace std;
#define N 100005
#define pb push_back
int n,m,index1;
bitset<N> inst;
vector<int> a[N],ind,indlow,com;
vector< vector<int> > c;
stack<int> st;
inline void citire()
{
	scanf("%d%d",&n,&m);
	ind.assign(n+3,0);
	indlow.resize(n+3);
	int x,y;
	for(int i=0; i<m; ++i)
	{
		scanf("%d%d",&x,&y);
		a[x].pb(y);
	}
}
void tarjan(int nod)
{
	ind[nod]=indlow[nod]=++index1;
	st.push(nod);
	inst[nod]=1;
	for(int i=0,lim=a[nod].size(); i<lim; ++i)
	{
		int nod1=a[nod][i];
		if(!ind[nod1])
		{
			tarjan(nod1);
			indlow[nod]=min(indlow[nod],indlow[nod1]);
		}
		else
		if(inst[nod1])
			indlow[nod]=min(indlow[nod],indlow[nod1]);
	}
	if(ind[nod]==indlow[nod])
	{
		com.clear();
		int nod1;
		do
		{
			nod1=st.top();
			st.pop();
			inst[nod1]=0;
			com.pb(nod1);
		}while(nod1!=nod);
		c.pb(com);
	}
}
inline void rezolva()
{
	for(int i=1; i<=n; ++i)
	{
		if(ind[i])
			continue;
		tarjan(i);
	}
}
inline void scrie()
{
	printf("%u\n",c.size());
	for(int i=0,lim=c.size(); i<lim; ++i)
	{
		for(int j=0,lim1=c[i].size(); j<lim1; ++j)
			printf("%d ",c[i][j]);
		printf("\n");
	}
}
int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	citire();
	rezolva();
	scrie();
	return 0;
}