Cod sursa(job #611578)

Utilizator auRSTARHreapca Aurelian auRSTAR Data 1 septembrie 2011 23:13:26
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<cstdio>
#include<vector>
#include<stack>
#define stiva stack<int>
#define minim(a,b) a<b?a:b
using namespace std;
vector<int>V[100010],componenta;
vector<vector<int> >SOL;
stiva S;
void read(),solve(),tarjan(int);
int n,m,a,i,b,viz[100010],ind[100010],curr=1,lowlink[100010],aux;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(;m;--m)
	{
		scanf("%d%d",&a,&b);
		V[a].push_back(b);
	}
}
void solve()
{
	for(i=1;i<=n;i++)
		if(!ind[i])tarjan(i);
	printf("%d\n",SOL.size());
	for(unsigned i=0;i<SOL.size();i++)
	{
		for(vector<int>::iterator it=SOL[i].begin();it!=SOL[i].end();it++)
			printf("%d ",*it);
		printf("\n");
	}
}
void tarjan(int X)
{
	ind[X]=curr;
	lowlink[X]=curr;
	++curr;
	S.push(X);viz[X]=1;
	for(vector<int>::iterator it=V[X].begin();it!=V[X].end();it++)
	{
		if(!ind[*it]){tarjan(*it);lowlink[X]=minim(lowlink[X],lowlink[*it]);}
		else if(viz[*it])lowlink[X]=minim(lowlink[X],lowlink[*it]);
	}
	if(lowlink[X]==ind[X])
	{
		componenta.resize(0);
		int aux;
		do
		{
			aux=S.top();
			componenta.push_back(aux);
			viz[aux]=0;
			S.pop();
		}while(aux!=X);
		SOL.push_back(componenta);
	}
}