StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I had fun with these problems! At least, 2 and 3.</p> <p>1) I'm not sure I fully understand, but I figure by "compute the connected components" you mean "build subsets of the vertices such that each subset is a connected component". If so, I think BFS or DFS would work depending on how you manage memory (ie. how you mark vertices you've already visited).</p> <p>2) [Edited]Here's an algorithm which, used on any acyclic directed graph, should number the vertices according to the "compact" definition and detect if the graph is in fact compact (ie. contains <strong>all</strong> edges (i, j) such that i < j for all (i, j) in [0, n-1]).</p> <ol> <li>Find all vertices with no incoming edges (since the graph is acyclic, we know there will be at least one of these). 1a. If there are more than one, terminate algorithm: the graph is not compact.</li> <li>Assign a number to it, starting from the lowest number available (0, for the first iteration).</li> <li>Remove this vertex from the graph, along with all edges outgoing from it.</li> <li>Go back to step 1, and repeat until all vertices are gone. If we reach that point without the algorithm terminating, then the graph is compact.</li> </ol> <p>(This is also O(n^2), btw - n searches over n vertices to find vertices without incoming edges - although this is only worst-case) At the end of this, all vertices will be numbered such that if it has incoming edges, the nodes from which they come will have a lower number than itself.</p> <p>3) Assuming the graph is already connected, here is an algorithm to make it biconnected:</p> <ol> <li>Find all vertices with only one edge (ie. endpoints).</li> <li>Arbitrarily select one of these.</li> <li>Draw edges from this selected vertex to all the other endpoint vertices. (I think this actually fits O(n). One search over n vertices to find endpoints, and we add less than n edges, since you can't have a connected graph consisting entirely of endpoints.)</li> </ol> <p>Voila! A biconnected graph! Remove any endpoint vertex, and the original connected graph is still intact; remove any other vertex, and we know that each segment is still connected through the endpoints.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload