Cod sursa(job #531306)

Utilizator siminescuPaval Cristi Onisim siminescu Data 9 februarie 2011 13:33:42
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<fstream>
#include<vector>
#include<stack>
#include<iterator>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

# define nmax 100002
# define min(a,b) ((a<b)? (a):(b))

vector <int> v[nmax],ctc;
vector <vector <int> > afis;
stack <int> S;
int N,M,idx[nmax],lowlink[nmax],indecs;
bool inS[nmax];

void citire()
{
	f>>N>>M;
	int i,j;
	for(;M;--M)
		f>>i>>j, v[i].push_back(j);
}
void tarzan(int nod)
{
	++indecs;
	idx[nod]=lowlink[nod]=indecs;
	S.push(nod), inS[nod]=1;
	vector <int>::const_iterator it;
	for(it=v[nod].begin();it!=v[nod].end();++it)
		if(!idx[*it])
			tarzan(*it),
			lowlink[nod]=min(lowlink[nod], lowlink[*it]);
		else if(inS[*it])
			lowlink[nod]=min(lowlink[nod], lowlink[*it]);
	if(idx[nod]==lowlink[nod])
	{
		int bla;
		ctc.clear();
		do{
			bla=S.top();
			S.pop(), inS[bla]=0;
			ctc.push_back(bla);
		}while(bla!=nod);
		afis.push_back(ctc);
	}
}
void afisare()
{
	int n,m,i,j;
	n=afis.size();
	g<<n<<'\n';
	for(i=0;i<n;++i)
	{
		m=afis[i].size();
		for(j=0;j<m;++j)
			g<<afis[i][j]<<' ';
		g<<'\n';
	}
}
int main()
{
	citire();
	int i;
	for(i=1;i<=N;++i)
		if(!idx[i]) tarzan(i);
	afisare();
	return 0;
}