Cod sursa(job #1358289)

Utilizator alexb97Alexandru Buhai alexb97 Data 24 februarie 2015 15:23:02
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

ifstream is("ctc.in");
ofstream os("ctc.out");

int n, m;
vector<vector<int>> g, gt;
vector<vector<int>> sol;
stack<int> stk;
vector<bool> s;
int nrc; 

void Df(int x);
void DfTrans(int x, int r);


int main()
{
	is >> n >> m;
	int x, y;
	int r = 0;
	sol = vector<vector<int>>(n+1);
	g = vector<vector<int>>(n+1);
	gt = vector<vector<int>>(n+1);
	s = vector<bool>(n+1);
	
	for(int i = 1; i<= m; ++i)
	{
		is >> x >> y;
		g[x].push_back(y);
		gt[y].push_back(x);
	}
	for(int i = 1; i <= n; ++i)
	{
		if( !s[i] )
			Df(i);
	}
	
	s.assign(n + 1, false); 
	
	while ( !stk.empty() )
	{
		int i = stk.top();
		stk.pop();
		if ( !s[i] )
		{
			r++;
			nrc++;
			DfTrans(i, r);
		}
	}
	
	os << nrc << '\n';
	for(int i = 1; i <= r; ++i )
	{
		for(vector<int>::iterator it = sol[i].begin(); it != sol[i].end(); ++it)
		{
			os << *it << ' ';
		}
		os << '\n';
	}
	is.close();
	os.close();
	return 0;
}

void Df(int x)
{
	s[x] = true;
	for(const auto & y : g[x])
		if(!s[y])
			Df(y);
	stk.push(x);
}

void DfTrans(int x, int r)
{
	s[x] = true;
	sol[r].push_back(x);
	//os << x << ' ';
	for(const auto & y: gt[x])
	{
		if(!s[y])
			DfTrans(y, r);
	}
}