796 – Critical Links

Problem Statement

Given an undirected graph, find its critical edges. A critical edge is one that when removed disconnects any two connected nodes.

The brute-force solution –removing an edge and checking for connectivity– will work. But this is an implementation using Tarjan’s DFS Bridge finding algorithm.

set<int> apNodes, apVis;
set<pair<int, int> > apEdges;
void articulationPointAndBridge(map<int, map<int, int> > &graph, int s) {
    map<int, int> parent, num_dfs, num_low;
    int children_s = 0, num_dfs_size = 0;
    stack<int> stk;
    parent[s] = s, stk.push(s);
    // dfs
    while (stk.size()) {
        int u = stk.top();
        // grey
        if (apVis.find(u) == apVis.end()) {
            num_dfs[u] = num_low[u] = num_dfs_size++;
            apVis.insert(u);
            children_s += u != s && parent[u] == s;
            for (map<int, int>::reverse_iterator v = graph[u].rbegin();
                 v != graph[u].rend(); ++v)
                // grey to white
                if (apVis.find(v->first) == apVis.end())
                    parent[v->first] = u, stk.push(v->first);
                // grey to grey
                else if (parent[u] != v->first)
                    num_low[u] = min(num_low[u], num_dfs[v->first]);
        }
        // black
        else {
            if (parent[u] != u) {
                // POINTS
                if (num_dfs[parent[u]] <= num_low[u])
                    apNodes.insert(parent[u]);
                // BRIDGES
                if (num_dfs[parent[u]] < num_low[u])
                    if (u < parent[u])
                        apEdges.insert(make_pair(u, parent[u]));
                    else
                        apEdges.insert(make_pair(parent[u], u));
                num_low[parent[u]] = min(num_low[parent[u]], num_low[u]);
            }
            stk.pop();
        }
    }
    apNodes.erase(s);
    if (children_s > 1)
        apNodes.insert(s);
}

int main() {
    string str;
    int n, a, b, m;
    while (cin >> n) {
        // input
        map<int, map<int, int> > graph;
        for (int i = 0; i < n; ++i) {
            cin >> a;
            cin >> str;
            stringstream ss(str.substr(1, str.length() - 2));
            ss >> m;
            for (int j = 0; j < m; ++j)
                cin >> b, graph[a][b] = graph[b][a] = 1;
        }
        // solve
        apVis.clear(), apEdges.clear(), apNodes.clear();
        for (map<int, map<int, int> >::iterator i = graph.begin();
             i != graph.end(); ++i)
            if (apVis.find(i->first) == apVis.end())
                articulationPointAndBridge(graph, i->first);
        // print
        cout << apEdges.size() << " critical links";
        for (set<pair<int, int> >::iterator i = apEdges.begin();
             i != apEdges.end(); ++i)
            cout << endl << i->first << " - " << i->second;
        cout << endl << endl;
    }
}

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)

11417 – GCD

Solution 1: The filthy nasty approach:

• Pre-calculate.

C++ rank 94.

#include <iostream>
#include <cstdlib>
#include <limits.h>
using namespace std;

unsigned int n, g[501] = { "http://pastebin.com/CFsnYiNy" };

int main() {
	while(cin >> n && n > 0)
		cout << g[n] << endl;
	return 0;
}

Solution 2: The wise guy approach:
This includes basic summations knowledge. The expression we want to evaluate is:

And, I’ll use as short for . This is actually how early mathematicians used to express the GCD.

is always . This holds for any integer and can be proved using the definition of the greatest common divisor:
If then and . Subtracting both gives:
. Which is: , hence, as we’re only dealing with positive integers. So, any two consecutive integers are co-prime.
Back to :

The term gives .

We can refer to the second term as where:

Which is:

Using Euclid’s algorithm, the term can be written as which is for . This is for even numbers and for odd numbers. A simple task.

Now, the problem lies in the first term . It’s not equal to .

Yes we’ve changed the summation indexes to look like but the quantity inside the summation must be .
That’s where I hit the wall, there’s no recursive method or any expression, not that I know of, that expresses in terms of . This stopped my adrenaline rush and I felt really miserable.
So we’ll have to go for some filthiness. We’ll pre-calculate and use it to evaluate recursively.
and the base case is .
Implementation in C++. This got rank 95! After all, filthiness is not that… well… filthy.

#include <iostream>
#include <cstdlib>
#include <limits.h>
using namespace std;

const int N = 502;
int G[N], g[N] = { "http://pastebin.com/Rea3tu3B" }

int get_G(int n) {
	// base case
	if (n <= 1)
		return 0;
	if (G[n] != -1)
		return G[n];
	// recursion
	return G[n] = (get_G(n - 1) + g[n - 2] + 1);
}

int main() {
	/*reset*/
	for (int i = 1; i < N; ++i)
		G[i] = -1;
	/*input*/
	int n;
	while (cin >> n && n != 0)
		cout << get_G(n) << endl;
	return 0;
}

If you could give me that relation between and , I’d be very grateful.