Cod sursa(job #1784757)

Utilizator ArkinyStoica Alex Arkiny Data 20 octombrie 2016 14:38:44
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<fstream>
#include<vector>
using namespace std;

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

vector<int> G[100010];
vector<int> G_T[100010];

vector<int> stk;

int v[100010], nr=0;

vector<int> comp_conex[100010];


void sort_top(int x)
{
	v[x] = 1;

	for (int i = 0;i < G[x].size();++i)
		if (!v[G[x][i]])
			sort_top(G[x][i]);

	stk.push_back(x);
}

void kosaraju(int x)
{ 
	v[x] = 1;

	for (int i = 0;i < G_T[x].size();++i)
		if (!v[G_T[x][i]])
			kosaraju(G_T[x][i]);

	comp_conex[nr].push_back(x);
}

int main()
{

	int N, M;

	in >> N >> M;

	for (int i = 1;i <= M;++i)
	{
		int x, y;
		in >> x >> y;

		G[x].push_back(y);
		G_T[y].push_back(x);
	}

	for (int i = 1;i <= N;++i)
		if (!v[i])
			sort_top(i);

	for (int i = 1;i <= N;++i)
		v[i] = 0;

	for (int i = stk.size() - 1;i >= 0;--i)
		if (!v[stk[i]])
		{
			++nr;
			kosaraju(stk[i]);
		}
	out << nr << '\n';
	for (int i = 1;i <= nr;++i)
	{
		for (int j = 0;j < comp_conex[i].size();++j)
			out << comp_conex[i][j] << " ";
		out << '\n';
	}

	return 0;
}