Cod sursa(job #470594)

Utilizator IrnukIrina Grosu Irnuk Data 14 iulie 2010 19:04:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.33 kb
#include<fstream>
#include<vector>
#include<list>
#include<queue>

#define NMAX 100005

using namespace std;
long n,m,d[NMAX],f[NMAX],vizitat[NMAX],total_scc;
long timpulet;
vector<list<long> > G,GT;
vector<list<long> > scc;
struct Vrf
{
	long nod;
	long tmp;
};

struct DereferenceCompareVrf : public std::binary_function<Vrf, Vrf, bool> 
{ 
    bool operator()(const Vrf lhs, const Vrf rhs) const 
    { 
        return lhs.tmp < rhs.tmp; 
    } 
};

priority_queue<Vrf,vector<Vrf>, DereferenceCompareVrf> heap;

void dfs(int x)
{
	vizitat[x]=1;
	list<long>::iterator itr;
	for(itr=G[x].begin(); itr!=G[x].end(); itr++)
		if(vizitat[*itr]==0)
		{
			timpulet+=1;
			d[*itr]=timpulet;
			vizitat[*itr]=1;
			dfs(*itr);
		}
	timpulet+=1;
	Vrf a;
	a.nod=x;
	a.tmp=timpulet;

	heap.push(a);
//	f[x]=timpulet;
	
}

void dfs_reverse(int x)
{
	vizitat[x]=1;
	scc[total_scc].push_back(x);
	f[x]=0;
	list<long>::iterator itr;
	for(itr=GT[x].begin(); itr!=GT[x].end(); itr++)
		if(vizitat[*itr]==0)
		{
		//	d[*itr]=++timpulet;
			vizitat[*itr]=1;
			dfs_reverse(*itr);
		}
	//f[x]=++timpulet;
	
}
int main()
{
	fstream fin,fout;
	long i,x,y;
	list<long> lista;

	fin.open("ctc.in",ios::in);
	fout.open("ctc.out",ios::out);
	
	fin>>n>>m;

	for(i=0;i<=n;i++)
	{
		G.push_back(lista);
		GT.push_back(lista);
		d[i]=f[i]=0;
	}

	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		G[x].push_back(y);
		GT[y].push_back(x);
	}

	for(i=1;i<=n;i++)
		if(vizitat[i]==0)
			dfs(i);

	for(i=1;i<=n;i++)
		vizitat[i]=0;

	long maxim=1,svI=0;
	scc.push_back(lista);

	while(!heap.empty())
	{
		Vrf el;
		el.nod=(heap.top()).nod;
		heap.pop();
		if(vizitat[el.nod]==0)
		{
			total_scc++;
			scc.push_back(lista);
			dfs_reverse(el.nod);
		}

	}
	//while(maxim!=0)
	//{
	//	maxim=0;
	//	for(i=1;i<=n;i++)
	//		if(f[i]>maxim)
	//		{
	//			svI=i;
	//			maxim=f[i];
	//		}
	//	if(maxim!=0)
	//	{
	//		total_scc++;
	//		scc.push_back(lista);
	//		dfs_reverse(svI);
	//	}
	//}
	
	vector<list<long> >::iterator vItr;
	list<long>::iterator lItr;

	fout<<total_scc<<'\n';
	vItr=scc.begin();
	vItr++;

	for(vItr=vItr; vItr!=scc.end(); vItr++)
	{

		for(lItr=(*vItr).begin(); lItr!=(*vItr).end(); ++lItr)
			fout<<*lItr<<" ";
		fout<<'\n';

	}

	fin.close();
	fout.close();
	return 0;
}