Cod sursa(job #629799)

Utilizator ELHoriaHoria Cretescu ELHoria Data 3 noiembrie 2011 23:47:41
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int MAXN = 100002;
int  N , M , x , y , indecs , scnt;
vector< vector<int> > C; 
vector<int> G[MAXN] , con , pre , id;
stack<int> S , P;

void read_data()
{
	for(fin>>N>>M;M;M--)
		fin>>x>>y , 
		G[x].push_back(y);
	pre.resize(N+1,-1) , id.resize(N+1,-1);
}

void gabow(const int node)
{
	pre[node] = indecs++;
	S.push(node) , P.push(node);
	for(vector<int>::const_iterator it=G[node].begin();it!=G[node].end();++it)
		if(pre[*it]==-1) gabow(*it);
		else
		if (id[*it]) while(pre[P.top()]>pre[*it]) P.pop();

		if(P.top() == node)
		{
			P.pop(); int currnod;
			con.clear();
			do{
				con.push_back( currnod = S.top());
				S.pop() , id[currnod] = scnt;
			} while(currnod!=node);
			C.push_back(con);
		} 
}

int main()
{
	read_data();
	for(int i=1;i<=N;++i)
		if(pre[i]==-1) 	gabow(i);

	fout<<C.size()<<'\n';
	for(int i=0;i<(int)C.size();++i)
	{
		for(int j=0;j<(int)C[i].size();++j)
			fout<<C[i][j]<<' ';
		fout<<'\n';
	}
	return 0;
}