Cod sursa(job #928488)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 26 martie 2013 14:29:15
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<fstream>
#include<vector>
using namespace std;

vector <int> a[100001],v,s;
vector <vector <int> > sol;
int d[100001],l[100001],n,m,i,j,x,y,p;
bool w[100001];

void df(int x)
{
	int i,y;
	d[x]=l[x]=++p;
	s.push_back(x);
	w[x]=1;
	for (i=0;i<a[x].size();i++)
	{
		y=a[x][i];
		if (l[y]==0)
		{
			df(y);
			d[x]=min(d[x],d[y]);
		}
		else if (w[y]==1)
			d[x]=min(d[x],l[y]);
	}
	if (d[x]==l[x])
	{
		v.resize(0);
		while (s.back()!=x)
		{
			v.push_back(s.back());
			w[s.back()]=0;
			s.pop_back();
		}
		v.push_back(s.back());
		w[s.back()]=0;
		s.pop_back();
		sol.push_back(v);
	}
}
	

int main()
{
	ifstream f("ctc.in");
	ofstream g("ctc.out");
	f >> n >> m;
	for (i=1;i<=m;i++)
	{
		f >> x >> y;
		a[x].push_back(y);
	}
	for (i=1;i<=n;i++)
		if (l[i]==0)
			df(i);
	g << sol.size() << "\n";
	for (i=0;i<sol.size();i++)
	{
		for (j=0;j<sol[i].size();j++)
			g << sol[i][j] << ' ';
		g << "\n";
	}
	return 0;
}