Cod sursa(job #2340149)

Utilizator AndreiBadescuBadescu Andrei-Octavian AndreiBadescu Data 9 februarie 2019 20:36:54
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
typedef unsigned int uint;

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

class Graph
{
	uint V;
	/// 0 - normal
	/// 1 - transposed
	vector<vector<uint>> adj[2];
	void DFS(uint node, vector<bool> &v, bool ok, stack<uint> &S);
public:
	Graph(uint V);
	void Add_edge(uint x, uint y);
	void Kosaraju();
};

Graph::Graph(const uint V)
{
	this->V = V;
	adj[0].assign(V + 1, vector<uint>());
	adj[1].assign(V + 1, vector<uint>());
}

void Graph::Add_edge(uint x, uint y)
{
	adj[0][x].emplace_back(y);
	adj[1][y].emplace_back(x);
}

void Graph::DFS(uint node, vector<bool> &v, bool ok, stack<uint> &S)
{
	v[node] = true;
	for (auto &i : adj[ok][node])
		if (!v[i])
			DFS(i,v,ok,S);

	S.push(node);
}

void Graph::Kosaraju()
{
	stack<uint> S;
	vector<bool> v(V + 1, false);

	for (uint i = 1; i <= V; ++i)
	{
		if (!v[i])
			DFS(i,v,0,S);
	}


	vector<stack<uint>> print;

	v.clear();
	v.assign(V + 1, false);
	while (!S.empty())
    {
		if (!v[S.top()])
		{
		    stack<uint> sol;
			DFS(S.top(), v, 1, sol);
			print.push_back(sol);
		}
		S.pop();
    }

	fout << print.size() << '\n';

	for (auto &i : print)
	{
		while (!i.empty())
		{
			fout << i.top() << ' ';
			i.pop();
		}
		fout << '\n';
	}
}

int main()
{
	ios::sync_with_stdio(false);

	uint n,m;
	fin >> n >> m;

	Graph G(n);

	for (uint x,y,i = 0; i < m; ++i)
	{
		fin >> x >> y;
		G.Add_edge(x,y);
	}

	G.Kosaraju();
}