10305 – Ordering Tasks

Given a set of dependent tasks, find the order in which these tasks have to be executed.

The solution is found via a topological sort.

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
#include <queue>
#include <map>
using namespace std;

vector<map<int, int> > graph;
vector<int> sortedNodes;

void topSort() {
	sortedNodes.clear();
	vector<int> inDegree = vector<int>(graph.size(), 0);
	for (size_t i = 0; i < graph.size(); ++i)
		for (map<int, int>::iterator itr = graph[i].begin(); itr != graph[i].end(); ++itr)
			++inDegree[itr->first];
	queue<int> q;
	for (size_t i = 0; i < graph.size(); ++i)
		if (inDegree[i] == 0)
			q.push(i);
	while (q.size()) {
		int p = q.front();
		sortedNodes.push_back(p), q.pop();
		for (map<int, int>::iterator itr = graph[p].begin(); itr != graph[p].end(); ++itr)
			if (!(--inDegree[itr->first]))
				q.push(itr->first);
	}
}

int main() {
	int n, m;
	while (cin >> n >> m && (n || m)) {
		// input
		graph.clear();
		for (int i = 0; i < n; ++i)
			graph.push_back(map<int, int>());
		for (int i = 0, x, y; i < m; ++i)
			cin >> x >> y, --x, --y, graph[x][y] = 1;
		// solve
		topSort();
		cout << (sortedNodes[0] + 1);
		for (int i = 1; i < n; ++i)
			cout << " " << (sortedNodes[i] + 1);
		cout << endl;
	}
	return 0;
}

Introduction to Binary Trees

Basic Definitions

• Binary Tree
  A binary tree is made of a set of nodes. This set can be empty or it can consist of a node called a root along with two disjoint subtrees.
• Disjoint subtrees
  Trees that have no nodes in common.
• Node
  A node contains a value and links to two (binary) other nodes called children (left and right). These links are called edges. A node also might link to its parent node.
• Descendant node
  Nodes of any subtree are descendants of its root.
• Ancestor node
  A root of a subtree is an ancestor of it’s nodes.
• Path from n₁ to n_k
  The path from n1 to nk is the sequence of nodes n1, n2 ... nk. Where each node ni in the sequence is a parent of node ni + 1 (each node is a parent of the next / going from the top downwards).
• Depth/Level of node M
  The length of the path between the root of the tree R and M. The root node R is at level 0.
• Height of a tree
  More than the depth of the deepest node in the tree by one. height = max(depth) + 1.
• Leaf/External node
  A node that has no children. Has neither right nor left subtree.
  !hasLeft AND !hasRight = !(hasLeft OR hasRight)
• Internal node
  A node that has at least one child. Has a right or a left subtree. Or both. An internal node is the opposite of an external node.
  hasLeft OR hasRight = !(!hasLeft AND !hasRight)
• Full tree
  A binary tree which consists of nodes that must satisfy one of the following conditions:
  • An internal node with two non-empty children.
  • A leaf.

  Each node must have either 0 or 2 children. Uni-child nodes aren’t allowed.

• Complete tree
  A binary tree which in which all the levels are full except the last level. You can think of it as a tree that is filled from left to right level by level.
  You might confuse a complete tree with a full tree. A little mind trick to memorize them is: the word complete is wider than the word full, so is the complete tree — always wider than the full tree–.

Full Binary Theorem

• The number of leaves in a non-empty full binary tree = number of internal nodes + 1
• The number of empty subtrees in a non-empty binary tree = number of nodes in the tree + 1

Proven by mathematical induction.

Traversal

A tree’s nodes are placed in such structure for a reason. We want to process the tree’s nodes — one by one — by visiting them in a certain order.
These ways/orders by which we visit the nodes are called traversals. A traversal on a tree generates a sequence of nodes in which each node appears once and only once. This is called an enumeration.
There are three types of traversal: pre-order, post-order and in-order. They’ll be explained using the following figure.

Imagine you’re starting from the root of the tree and draw a border around the tree parallel to the edges and surrounding each branch as shown.
Whenever you pass through the left of a node, you’re in pre-order. When you are below a node, you’re in in-order. If you are to the right of a node, you’re in post-order.

• Pre-Order

The algorithm goes as follows:

preoreder(node)
	if(node == null)
		return;
	do(node)
	preorder(node.left)
	preorder(node.right)

• In-Order

The algorithm goes as follows:

inoreder(node)
	if(node == null)
		return;
	inorder(node.left)
	do(node)
	inorder(node.right)

• Post-Order

The algorithm goes as follows:

postoreder(node)
	if(node == null)
		return;
	postorder(node.left)
	postorder(node.right)
	do(node)

You can do these traversals simultaneously in a more general manner instead of only one at a time by gluing them together. The procedure should looks like this:

traverse(node)
	if(node == null)
		return;
	doPreOrder(node)
	traverse(node.left)
	doInOrder(node)
	traverse(node.right)
	doPostOrder(node)