Cod sursa(job #928416)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 26 martie 2013 14:00:00
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 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;

void df(int x)
{
	int i,y;
	d[x]=l[x]=++p;
	s.push_back(x);
	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
			d[x]=min(d[x],d[y]);
	}
	if (d[x]==l[x])
	{
		v.resize(0);
		while (s.back()!=x)
		{
			v.push_back(s.back());
			s.pop_back();
		}
		v.push_back(s.back());
		s.pop_back();
		sol.push_back(v);
	}
	p--;
}
	

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