Cod sursa(job #2377138)

Utilizator AndreiBadescuBadescu Andrei-Octavian AndreiBadescu Data 8 martie 2019 22:14:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>

#define N 100001

using namespace std;
typedef unsigned int uint;

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

uint n, m, timp, lowlink[N], v[N];
bool inStack[N];
vector<vector<uint>> adj, sol;
stack<uint> S;

void SSC(uint node)
{
	S.push(node);

	inStack[node] = true;
	lowlink[node] = v[node] = ++timp;

	for (auto &i : adj[node])
	{
		if (!v[i])
		{
			SSC(i);
			lowlink[node] = min(lowlink[node], lowlink[i]);
		}
		else if (inStack[i])
		{
			lowlink[node] = min(lowlink[node], lowlink[i]);
		}
	}

	if (lowlink[node] == v[node])
	{
		sol.emplace_back(vector<uint>());
		while (S.top() != node)
		{
			sol.back().emplace_back(S.top());
			inStack[S.top()] = false;
			S.pop();
		}

		sol.back().emplace_back(S.top());
		inStack[S.top()] = false;
		S.pop();
	}
}

void Tarjan()
{
	for (uint i = 1; i <= n; ++i)
	{
		if (!v[i])
			SSC(i);
	}

	fout << sol.size() << '\n';
	for (auto &i : sol)
	{
		for (auto &j : i)
			fout << j << ' ';
		fout << '\n';
	}
}

int main()
{
	fin >> n >> m;

	adj.assign(n + 1, vector<uint>());

	for (uint x,y,i = 0; i < m; ++i)
	{
		fin >> x >> y;
		adj[x].emplace_back(y);
	}

	Tarjan();
}