Tag Archives: connected

Tarjan’s Strongly Connected Components Algorithm

I just added a program that finds the strongly connected components of a graph using Tarjan’s Algorithm.

A strongly connected component of a graph is a subgraph S of G where every pair of nodes, u and v in S there is a path from u to v and a path from v to u.

To find these strongly connected components we implement Tarjan’s algorithm. The idea behind Tarjan’s algorithm is to begin by running a depth first search from an arbitrary node in the graph, labeling nodes reachable from this start node in the order they are reached. The algorithm is also interested in the “oldest” node that could be reached by a given node. This is indicated by the keeping track of the lowest label that can be reached from that node. We will call the first property label(v) and the second lowlink(v).

When the algorithm starts label(v) is the same as lowlink(v) whenever a node is discovered. As the algorithm is executed, the DFS is being run on each discovered node, which in turn updates the lowlink(v) property telling of (older) nodes that can be reached. If an older node can be reached, then we update lowlink. If we reach a node that cannot connect to any older nodes after the DFS call, i.e if label(v) is the same a lowlink(v), then this means that this node does not have a path to any node with a lower label. So this node will be the first node of a new strongly connected component.

Feel free to check it out an let me know what you think in the comments below.

Shade The Cells Puzzle

A friend described this puzzle to me and I enjoyed it so much that I just had to write a script so that I could play it more.

The rules of this puzzle are simple. Cells can be in one of three states:

An UNSHADED (white) cell means that you have not considered this cell yet.
A DARK GREY SHADED cell means that the sum of the dark grey shaded cells in that row and column must equal the number in that cell.
A LIGHT GREY SHADED cell means that the sum of the dark grey shaded cells in all the connected cells must equal the number in that cell.

I Hope you Enjoy