Tarjan Subtree Decomposition

graph.h

#ifndef GRAPH_H_
#define GRAPH_H_

#include <algorithm>
#include <cstdio>
#include <string>
#include <stdexcept>

namespace sp {
	class Graph {
		public:

			struct Arc {
				int head;
				int weight;
			};

			Graph() {
				arcs = 0;
				firstArcs = 0;
			}
			
			~Graph() {
				if (arcs) {
					delete[] arcs;
				}
				if (firstArcs) {
					delete[] firstArcs;
				}
			}
			
			void load(const std::string &fileName) {
				FILE *f = fopen(fileName.c_str(), "r");
				if (f == NULL) {
					throw std::runtime_error("can't open the input file");
				}
				if (fscanf(f, "%d%d", &numNodes, &numArcs) != 2) {
					throw std::runtime_error("can't read numNodes or numArcs");
				}
				if (numNodes <= 0) {
					throw std::runtime_error("numNodes <= 0");
				}	
				if (numArcs < 0) {
					throw std::runtime_error("numArcs < 0");
				}
				InternalArc *readArcs = new InternalArc[numArcs];
				for (int i = 0; i < numArcs; ++i) {
					if (fscanf(f, "%d%d%d", &readArcs[i].tail, &readArcs[i].head, &readArcs[i].weight) != 3) {
						throw std::runtime_error("can't read tail, head or weight");
					}
					if (readArcs[i].tail < 0 || readArcs[i].tail >= numNodes) {
						throw std::runtime_error("invalid tail");
					}
					if (readArcs[i].head < 0 || readArcs[i].head >= numNodes) {
						throw std::runtime_error("invalid head");
					}
				}
				std::sort(readArcs, readArcs + numArcs);
				firstArcs = new Arc*[numNodes + 1];
				arcs = new Arc[numArcs];
				for (int i = 0; i < numArcs; ++i) {
					arcs[i].head = readArcs[i].head;
					arcs[i].weight = readArcs[i].weight;
				}
				int curArc = 0;
				for (int i = 0; i < numNodes; ++i) {
					firstArcs[i] = &arcs[curArc];
					while (curArc < numArcs && readArcs[curArc].tail == i) {
						curArc++;
					}
				}
				firstArcs[numNodes] = &arcs[curArc];
				delete[] readArcs;
				if (fclose(f) == EOF) {
					throw std::runtime_error("can't close the input file");
				}
			}
			
			inline int getNumNodes() const {
				return numNodes;
			}
			
			inline std::pair<Arc*, Arc*> getOutgoingArcs(int node) {
				return std::make_pair(firstArcs[node], firstArcs[node + 1]);
			}
			
		private:
		
			struct InternalArc {
				int tail;
				int head;
				int weight;
				
				bool operator<(const InternalArc &he) const {
					return std::make_pair(tail, head) < std::make_pair(he.tail, he.head);
				}
			};
			
			int numNodes;
			int numArcs;
			Arc *arcs;
			Arc **firstArcs;
	};
}

#endif

tarjan.cpp

#include "graph.h"

#include <cassert>
#include <limits>
#include <utility>

int main() {
	sp::Graph g;
	g.load("input.txt");
	int time1 = clock();
	int n = g.getNumNodes();
	long long *d = new long long[n];
	for (int i = 0; i < n; ++i) {
		d[i] = std::numeric_limits<long long>::max();
	}
	int *next = new int[n];
	int *prev = new int[n];
	int *degree = new int[n];
	int *q = new int[n + 1];
	int *type = new int[n];
	for (int i = 0; i < n; ++i) {
		type[i] = 0;
	}
	int *p = new int[n];
	for (int i = 0; i < n; ++i) {
		p[i] = -1;
	}
	int ql = 0, qr = 0;
	
	d[0] = 0;
	next[0] = prev[0] = 0;
	degree[0] = 0;
	q[qr++] = 0;
	type[0] = 1;

	int nodesScanned = 0;
	int arcsScanned = 0;
	int arcsRelaxed = 0;
	int curQueueSize = 1;
	int maxQueueSize = 1;

	while (ql != qr) {
		int curNode = q[ql++];
		if (ql == n + 1) ql = 0;
		curQueueSize--;
		if (type[curNode] == 0) continue;
		nodesScanned++;
		std::pair<sp::Graph::Arc*, sp::Graph::Arc*> its = g.getOutgoingArcs(curNode);
		for (sp::Graph::Arc* a = its.first; a != its.second; ++a) {
			arcsScanned++;
			int he = a->head;
			if (d[curNode] + a->weight >= d[he]) continue;
			arcsRelaxed++;
			long long delta = d[he] - d[curNode] - a->weight;
			d[he] = d[curNode] + a->weight;
			if (type[he] != 1) {
				q[qr++] = he;
				if (qr == n + 1) qr = 0;
				curQueueSize++;
				if (curQueueSize > maxQueueSize) {
					maxQueueSize = curQueueSize;
				}
			}
			if (type[he] != 0) {
				int curSubtreeNode = next[he];
				int score = degree[he];
				while (score != 0) {
					type[curSubtreeNode] = 0;
					d[curSubtreeNode] -= delta - 1;
					score--;
					score += degree[curSubtreeNode];
					curSubtreeNode = next[curSubtreeNode];
				}
				next[prev[he]] = curSubtreeNode;
				prev[curSubtreeNode] = prev[he];
				if (p[he] != -1) degree[p[he]]--;
			}
			prev[he] = curNode;
			next[he] = next[curNode];
			prev[next[he]] = he;
			next[prev[he]] = he;
			degree[he] = 0;
			degree[curNode]++;
			type[he] = 1;
			p[he] = curNode;
		}
		type[curNode] = 2;
	}
	printf("%.3lf\n", (clock() - time1 + 0.0) / (CLOCKS_PER_SEC + 0.0));
	for (int i = 0; i < n; ++i) {
		std::pair<sp::Graph::Arc*, sp::Graph::Arc*> its = g.getOutgoingArcs(i);
		for (sp::Graph::Arc* a = its.first; a != its.second; ++a) {
			if (a->weight + d[i] - d[a->head] < 0) {
				throw std::runtime_error("invalid distances");
			}
			if (p[a->head] == i && a->weight + d[i] - d[a->head] != 0) {
				throw std::runtime_error("tree edge with non-zero reduced cost");
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		if (p[i] == -1 && i) {
			throw std::runtime_error("p[v] == null and v != s");
		}
	}
	delete[] type;
	delete[] q;
	delete[] d;
	delete[] next;
	delete[] prev;
	delete[] degree;
	printf("nodesScanned = %d\n", nodesScanned);
	printf("arcsScanned = %d\n", arcsScanned);
	printf("arcsRelaxed = %d\n", arcsRelaxed);
	printf("maxQueueSize = %d\n", maxQueueSize);
	return 0;
}