Episode 23 - Strongly Connected Components

This week's episode will expand upon the technique involving low links to directed graphs. The result is Tarjan's strongly connected components algorithm. I'll be addressing how to extract these components and some additional helpful properties that are implicit to the algorithm.

Here are a few problems you can try solving involving SCC's:

• Proving Equivalences
• Field Plan

See you live! (time, stream)

Episode 22 - Biconnected Decompositions

In this week's episode I will be discussing the types of meta-graphs that can be formed from 2-edge-connected and 2-vertex-connected components.

Here are a few problems that are relevant to this technique:

• Mining Your Own Business
• It Takes a Village
• Lucky Cities
• Unique Path

I will only be discussing a subset of these problems. You may find the others useful to solve on your own to practice this technique.

See you live! (time, stream)

Episode 21 - DFS Lowlink

Algorithms Live! is returns! Both the ICPC World Finals and USACO camp were excellent. Thank you to anyone who reached out and said hello at WF. It was fun meeting some of you and I received many great suggestions for improving the show. Meeting USACO campers was exciting as well. I'm happy to see these videos are relevant and useful for IOI training. It was a blast hanging out and discussing problems/techniques while writing as many challenging cow themed problems as possible.

Now it is time to resume making episodes. This week, I will be exploring some useful techniques for modifying depth first search on undirected graphs. This will allow us to extract articulation points, bridges, and 2-vertex/edge connected components, efficiently. I'll also be going over some tricks for making theses techniques more resilient to parallel edges and self-loops. Better yet, I'll implement these techniques. :)

I'll be expanding on different uses for this technique and some neat problems related to them in future weeks.

See you live! (time, stream)