#include <map>
#include <set>
#include <vector>
#include <string>
#include <exception>
#include <queue>
#include <stack>
const int INF = 2e9;
class VoidVertex : public std::exception {
public:
explicit VoidVertex (int vertex) {
msg = " vertex was not found in the graph!";
msg = std::to_string(vertex) + msg;
}
const char* what() const noexcept override {
return msg.c_str();
}
private:
std::string msg;
};
class DuplicateVertex : public std::exception {
public:
explicit DuplicateVertex (int vertex) {
msg = " vertex was already found in the graph!";
msg = std::to_string(vertex) + msg;
}
const char* what() const noexcept override {
return msg.c_str();
}
private:
std::string msg;
};
class Edge {
public:
Edge (int src, int dest, int label);
Edge (const Edge &other) = delete;
Edge& operator = (const Edge &other) = delete;
int getSrc () const;
int getDest () const;
int getLabel() const;
void setLabel(int label);
private:
~Edge();
int source;
int destination;
int label;
friend class Graph;
};
class Graph {
public:
Graph ();
Graph (const Graph &other);
Graph& operator = (const Graph &other) = delete;
~Graph ();
void addVertex (int vertex);
void addEdge (int src, int dest, int label = 0);
void removeEdge (int src, int dest);
void removeVertex (int vertex);
bool isVertex (int vertex) const;
int getSize () const;
int getEdgeSize () const;
int getMaxVertex() const;
Edge* getEdge (int src, int dest);
int getInDegree (int vertex);
int getOutDegree(int vertex);
std::vector <int> getVertices () const;
std::vector <Edge*> getInboundEdges (int vertex);
std::vector <Edge*> getOutboundEdges (int vertex);
private:
int edgesCount;
std::map <int, std::vector <Edge*>> inbounds;
std::map <int, std::vector <Edge*>> outbounds;
void vertexValidation(int vertex) const;
};
Graph* readGraph (const std::string &path, bool label = true, bool oneIndexed = false);
void writeGraph (const std::string &path, Graph *graph, bool label = true);
Graph* getRandomGraph(int vertexSize, int edgeSize);
void BFS(Graph *graph, int *dist, int *parent, int src);
class TarjanComputation {
public:
struct VertexData {
int discovery;
int lowLink;
void updateLow (int value) { lowLink = std::min(lowLink, value); }
bool isCritical () const { return discovery == lowLink; }
};
explicit TarjanComputation(Graph *graph);
const std::vector <std::vector <int>>& getComponents();
private:
int size;
Graph *graph;
std::vector <VertexData> data;
std::vector <bool> inStack;
std::stack <int> stack;
std::vector <std::vector <int>> components;
void DFS(int vertex);
void addComponent(int vertex);
};
#include <algorithm>
#include <fstream>
#include <chrono>
#include <random>
Edge::Edge(int src, int dest, int label) : source(src), destination(dest), label(label) {
}
Edge::~Edge() = default;
int Edge::getSrc () const { return this->source; }
int Edge::getDest () const { return this->destination; }
int Edge::getLabel () const { return this->label; }
void Edge::setLabel(int _label) {
this->label = _label;
}
Graph::Graph() : edgesCount (0) {
}
Graph::Graph(const Graph &other) : Graph() {
for (auto &vertex : other.getVertices())
this->addVertex(vertex);
for (auto &it : other.outbounds) {
for (auto &edge : it.second) {
this->addEdge(edge->getSrc(), edge->getDest(), edge->getLabel());
}
}
}
Graph::~Graph() {
for (auto &it : this->getVertices()) {
for (auto &edge : this->outbounds[it])
delete edge;
}
}
void Graph::addVertex(int vertex) {
if (this->inbounds.find(vertex) != this->inbounds.end()) throw DuplicateVertex(vertex);
this->inbounds[vertex] = std::vector <Edge*> ();
this->outbounds[vertex] = std::vector <Edge*> ();
}
void Graph::addEdge(int src, int dest, int label) {
this->vertexValidation(src);
this->vertexValidation(dest);
if (this->getEdge(src, dest) != nullptr) return;
auto edge = new Edge(src, dest, label);
this->outbounds[src].push_back(edge);
this->inbounds[dest].push_back(edge);
++ this->edgesCount;
}
void Graph::removeEdge(int src, int dest) {
this->vertexValidation(src);
this->vertexValidation(dest);
auto edge = this->getEdge(src, dest);
if (edge == nullptr) return;
this->outbounds[src].erase(std::find(outbounds[src].begin(), outbounds[src].end(), edge));
this->inbounds[dest].erase(std::find(inbounds[dest].begin(), inbounds[dest].end(), edge));
delete edge;
-- this->edgesCount;
}
void Graph::removeVertex(int vertex) {
this->vertexValidation(vertex);
for (auto &it : this->getVertices()) {
this->removeEdge(it, vertex);
this->removeEdge(vertex, it);
}
this->outbounds.erase(vertex);
this->inbounds.erase(vertex);
}
int Graph::getSize () const { return this->inbounds.size(); }
int Graph::getEdgeSize () const { return this->edgesCount; }
int Graph::getInDegree (int vertex) {
this->vertexValidation(vertex);
return this->inbounds[vertex].size();
}
int Graph::getOutDegree (int vertex) {
this->vertexValidation(vertex);
return this->outbounds[vertex].size();
}
Edge* Graph::getEdge(int src, int dest) {
this->vertexValidation(src);
this->vertexValidation(dest);
for (auto &edge : this->getOutboundEdges(src)) {
if (edge->getDest() == dest)
return edge;
}
return nullptr;
}
int Graph::getMaxVertex() const {
if (this->getSize() == 0) throw std::exception();
auto vertices = this->getVertices();
auto max = vertices[0];
for (auto &it:vertices) max = std::max(max, it);
return max;
}
std::vector <int> Graph::getVertices() const {
std::vector <int> vertices;
for (auto &it : this->inbounds) vertices.push_back(it.first);
return vertices;
}
std::vector <Edge*> Graph::getInboundEdges(int vertex) {
this->vertexValidation(vertex);
std::vector <Edge*> edges;
for (auto &it : this->inbounds[vertex]) edges.push_back(it);
return edges;
}
std::vector <Edge*> Graph::getOutboundEdges(int vertex) {
this->vertexValidation(vertex);
std::vector <Edge*> edges;
for (auto &it : this->outbounds[vertex]) edges.push_back(it);
return edges;
}
void Graph::vertexValidation(int vertex) const {
if (this->outbounds.find(vertex) == this->outbounds.end()) throw VoidVertex(vertex);
}
bool Graph::isVertex(int vertex) const {
return (this->outbounds.find(vertex) != this->outbounds.end());
}
Graph* readGraph(const std::string &path, bool label, bool oneIndexed) {
auto graph = new Graph();
std::ifstream inputFile(path);
int N, M;
inputFile >> N >> M;
for (int i=0; i<N; ++i) graph->addVertex(i);
for (int i=0, x, y, c; i<M; ++i) {
inputFile >> x >> y;
if (label) inputFile >> c;
else c = 0;
if (oneIndexed) --x, --y;
graph->addEdge(x, y, c);
}
inputFile.close();
return graph;
}
void writeGraph(const std::string &path, Graph *graph, bool label) {
std::ofstream outputFile(path);
int N = graph->getMaxVertex() + 1;
outputFile << N << ' ' << graph->getEdgeSize() << '\n';
for (auto &vertex : graph->getVertices()) {
for (auto &edge : graph->getOutboundEdges(vertex)) {
outputFile << edge->getSrc() << ' ' << edge->getDest();
if (label) outputFile << ' ' << edge->getLabel() << '\n';
else outputFile << '\n';
}
}
outputFile.close();
}
Graph* getRandomGraph(int vertexSize, int edgeSize) {
static std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
auto graph = new Graph();
for (int i=0; i<vertexSize; ++i) graph->addVertex(i);
int counter = 0;
if (edgeSize < 0 || edgeSize > vertexSize * vertexSize) throw std::exception();
while (counter < edgeSize) {
int x = std::uniform_int_distribution<int> (0, vertexSize-1) (rng);
int y = std::uniform_int_distribution<int> (0, vertexSize-1) (rng);
int c = std::uniform_int_distribution<int> (0, 100) (rng);
if (graph->getEdge(x, y) == nullptr)
graph->addEdge(x, y, c), counter += 1;
}
return graph;
}
void BFS(Graph *graph, int *dist, int *parent, int src) {
int N = graph->getMaxVertex() + 1;
std::queue <int> queue;
for (int i=0; i<N; ++i)
dist[i] = INF, parent[i] = i;
queue.push(src);
dist[src] = 0;
while (!queue.empty()) {
auto vertex = queue.front();
queue.pop();
for (auto &edge : graph->getOutboundEdges(vertex)) {
auto other = edge->getDest();
if (dist[other] != INF) continue;
parent[other] = vertex;
dist[other] = dist[vertex] + 1;
queue.push(other);
}
}
}
TarjanComputation::TarjanComputation(Graph *graph) : graph(graph) {
size = graph->getSize();
}
void TarjanComputation::DFS(int vertex) {
static int _time = 0;
data[vertex].discovery = data[vertex].lowLink = ++ _time;
inStack[vertex] = true;
stack.push(vertex);
for (auto &edge : graph->getOutboundEdges(vertex)) {
auto other = edge->getDest();
if (data[other].discovery == 0) {
DFS(other);
data[vertex].updateLow(data[other].lowLink);
}
else if (inStack[other]) {
data[vertex].updateLow(data[other].lowLink);
}
}
if (data[vertex].isCritical()) {
addComponent(vertex);
}
}
void TarjanComputation::addComponent(int vertex) {
components.emplace_back(std::vector <int>());
while (!stack.empty() && stack.top() != vertex) {
components.back().push_back(stack.top());
inStack[stack.top()] = false;
stack.pop();
} components.back().push_back(stack.top());
inStack[stack.top()] = false;
stack.pop();
}
const std::vector<std::vector<int>> &TarjanComputation::getComponents() {
static bool initialized = false;
if (!initialized) {
initialized = true;
inStack.resize(this->size);
data.resize(this->size);
for (auto &node : graph->getVertices()) {
if (data[node].discovery == 0)
DFS(node);
}
}
return components;
}
int main() {
std::ofstream output("ctc.out");
auto graph = readGraph("ctc.in", false, true);
auto tarjan = TarjanComputation(graph);
auto scc = tarjan.getComponents();
output << scc.size() << '\n';
for (auto &comp : scc) {
for (auto &node : comp) {
output << node+1 << ' ';
} output << '\n';
}
delete graph;
output.close();
return 0;
}