Cod sursa(job #519120)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 4 ianuarie 2011 00:39:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include<fstream>
#include<vector>
#include<stack>
using namespace std;

#define NMAX 100010

const char infile[]="ctc.in";
const char outfile[]="ctc.out";
vector<int> C[NMAX];
int N,M;

vector<int> G[NMAX];
stack<int> S,P;
int order[NMAX];
bool viz[NMAX];
int contor=1;
int CTC=0;

void Gabow(int v)
{
	S.push(v);
	P.push(v);
	order[v]=contor;
	contor++; 
	for(unsigned int i=0;i<G[v].size();i++)
	{
		if(order[G[v][i]] == 0)
		{
			Gabow(G[v][i]);
		}
		else if(!viz[G[v][i]])
		{
			while(!P.empty() && order[P.top()] > order[G[v][i]])
			{
				P.pop();
			}
		}
	}
	if(P.top() == v)
	{
		CTC++;
		while(S.top() != v)
		{
			C[CTC].push_back(S.top());
			viz[S.top()]=1;
			S.pop();
		}
		viz[S.top()]=1;
		C[CTC].push_back(S.top());
		S.pop();
		P.pop();
	}
}

void citire()
{
	fstream fin(infile,ios::in);
	fin>>N>>M;
	int x,y;
	for(int i=1;i<=M;i++)
	{
		fin>>x>>y;
		G[x].push_back(y);
	}

	fin.close();
}

void afisare()
{
	fstream fout(outfile,ios::out);
	fout<<CTC<<"\n";
	for(int i=1;i<=CTC;i++)
	{
		for(vector<int>::iterator itr=C[i].begin();itr!=C[i].end();itr++)
		{
			fout<<*itr<<" ";
		}
		fout<<"\n";
	}
	fout.close();
}

int main()
{
	citire();
	for(int i=1;i<=N;i++)
		if(!order[i])
			Gabow(i);
	afisare();





}