Cod sursa(job #470534)

Utilizator IrnukIrina Grosu Irnuk Data 14 iulie 2010 14:52:09
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include<fstream>
#include<vector>
#include<list>

#define NMAX 100005

using namespace std;
long n,m,d[NMAX],f[NMAX],vizitat[NMAX],tm,total_scc;
vector<list<long> > G,GT;
vector<list<long> > scc;
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)
		{
			tm+=1;
			d[*itr]=++tm;
			vizitat[*itr]=1;
			dfs(*itr);
		}
	tm+=1;
	f[x]=tm;
	
}

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]=++tm;
			vizitat[*itr]=1;
			dfs_reverse(*itr);
		}
	//f[x]=++tm;
	
}
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);
	}

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

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

	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;
}