Cod sursa(job #961719)

Utilizator predatorGigi Valoare predator Data 12 iunie 2013 19:20:57
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<fstream>
#include<deque>
#include<vector>
#define NM 100010
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int t,i,k,key,j,n,m,x,y;
int viz[NM];
vector<int> sol[NM];
vector<int> u[NM];
vector<int> v[NM];
deque<int> s;
void dfs1(int x)
{
	vector<int>::iterator it;
	for(it=v[x].begin();it!=v[x].end();++it)
	{
		if(!viz[*it])
		{
			viz[*it]=k;
			dfs1(*it);
		}
	}
	s.push_back(x);
}
void dfs2(int x)
{
	vector<int>::iterator it;
	sol[t].push_back(x);
	for(it=u[x].begin();it!=u[x].end();++it)
	{
		if(viz[*it]==key)
		{
			viz[*it]=0;
			dfs2(*it);
		}
	}
}
int main ()
{
	f>>n>>m;
	for(i=1;i<=m;++i)
	{
		f>>x>>y;
		v[x].push_back(y);
		u[y].push_back(x);
	}
	for(i=1;i<=n;++i)
	{
		if(!viz[i])
		{
			++k;
			dfs1(i);
		}
	}
	while(!s.empty())
	{
		while(!s.empty()&&!viz[s.back()])
			s.pop_back();
		if(s.empty())
			break;
		key=viz[s.back()];
		viz[s.back()]=0;
		++t;
		dfs2(s.back());
	}
	g<<t<<"\n";
	for(i=1;i<=t;++i)
	{
		for(j=0;j<sol[i].size();++j)
			g<<sol[i][j]<<" ";
		g<<"\n";
	}
	return 0;
}