Indian National Olympiad in Informatics
Online Programming Contest, 5-6 February 2005
IARCS home > OLYMPIAD
Advanced Division
Solution to Problem 2: Critical Intersections
This problem is just a cloaked version of a well known problem
about graphs. Let us first see, how to model this problem via
graphs.
Let us recall, from the solution to the "The Great Escape
Problem" of October 2004, the basic definitions regarding graphs:
A graph, say G, consists of two sets, a set of vertices or nodes
(V) and a set of edges (E). The set of vertices could be given
finite set. Each edge is a set consisting of two vertices. We
may interpret the set of edges as describing which pairs of
vertices are "neighbours".
Example: Here is a graph G = (V,E) with 7 vertices and 7 edges:
V = { 1,2,3,4,5,6,7 }
E = { {1,2},{1,3},{2,3},{3,4},{5,6},{5,7},{6,7} }
It is often convenient to draw graphs with boxes or circles to
represent the nodes and lines/curves connecting boxes/circles to
denote edges:
--- --- ---
| 1 |---------| 2 | | 7 |
--- /--- /---\
| / / \
| /-----/ / \
| / / \
---/ --- ---/ \ ---
| 3 |--------| 4 | | 5 |------------| 6 |
--- --- --- ---
Note that the placement of the boxes or the style of drawing the
edges are irrelevant. The "real" graph is given by the two sets V
and E and the picture is just to help us think.
A path in a graph is a sequence of vertices v1,v2,...,vk such
that {v1,v2}, {v2,v3} ... {v{k-1}vk} are edges. For example,
1,2,3,4 is a path in the above graph. The length of a path is the
number of edges in the path. For example, the length of the path
1,2,3,4 is 3.
We say that two vertices u and v are connected if there is a path
u=v_1, v_2, ..., v_k = v. In this case we say that v is
reachable from u (and u is reachable from v, since v_k v_{k-1}
... v_1 is a path from v to u).
We can think of the intersections and roads of Siruseri as a
graph. The vertices of this graph are the intersections of
Siruseri and the edges are the streets. Thus, an intersection is
reachable from another if and only if it is reachable in the
graph theoretic sense (described above).
Notice that we have been assured that initially every
intersection is reachable from every other intersection. A graph
in which every vertex is reachable from every other vertex is
called a "connected graph".
(The example graph defined above is not connected, since there is
no path from vertex 1 to vertex 7, for example, and thus it
cannot represent the intersections and streets of Siruseri.)
What is a critical intersection? Recall, that an intersection Y
is critical if there are two other intersections X and Z such
that all the routes from X to Z go through Y. (Since streets are
bidirectional, it follows that all the routes from Z to X also go
through Y). In the language of graphs, a vertex Y is a critical
intersection if there are vertices X and Z such that all the
paths from X to Z go through Y (i.e. Y appears in any path
beginning at X and ending in Y). Such vertices are called
"Articulation Points" in the language of graphs. Our aim is to
count the number of articulation points in the graph representing
the intersections and roads of Siruseri.
So how do we find whether a vertex Y in a graph G is an
articulation point? Suppose we drop Y (and all the edges incident
on it) from G and get the graph
G-Y = ( V - {Y}, E - {{X,Y} | X in V} ).
If Y is an articulation point then, G-Y is no longer a connected
graph. Conversely, if Y is any vertex in a connected graph G
such that G-Y is not connected then Y is an articulation point of
G. Thus, to determine whether Y is an articulation point, it
suffices to check if the graph G-Y is connected.
This can be done, for example, by the breadth-first search
algorithm described in the solution to the "The Great Escape"
problem from October 2004 problem set in time proportional to N*N
where N is the number of vertices. We can repeat this for each Y
to determine if it is an articulation point. The overall time
taken would thus be N*N*N.
We now describe a different algorithm called depth-first search
algorithm to explore the vertices of a graph and determine
whether it is connected. Like breadth-first search it takes time
proportional to N*N to determine if the graph is connected
(actually time proportional to the number of edges, just like
breadth-first search, but we leave that discussion for later.)
However, it is easier to implement than the breadth-first search
and has other interesting properites.
Recall that the breadth-first search algorithm visits the
vertices of the graph as follows: visit every neighbour of the
current vertex, then visit all the neighbours of the neighbours
and so on. It unravels the graph level by level --- first the
vertex itself, then the vertices at distance 1, then the vertices
at distance 2 and so on. On the other hand, the depth-first
search explores the graph by going as far as possible via a
picked neighbour (cutting through many levels) before
backtracking and exploring other neighbours.
The depth-first search algorithm is rather easy to understand and
here is its code:
============================================================================
/* Mark all vertices as unvisited */
for each vertex v in G {
Visited[v] = 0
}
dfs(u) /* start the dfs algorithm at some vertex u */
/* if the graph is connected then the dfs would have visited
all the vertices. Otherwise there would be unvisited vertices */
if there is vertex v with Visited[v]=0 then {
print "Graph Not Connected"
}
else {
print "Graph is Connected"
}
/* The dfs algorithm */
dfs(v) {
if (Visited[v]=1) then return /* v has been visited in the past*/
Visited[v] = 1 /* visit v */
DFSNo[v] = curr /* v is the curr'th vertex visited */
curr = curr + 1
for each neighbour w of v do {
dfs(w)
}
}
--------------------------------------------------------------------------
To illustrate how this algorithm works, here is a graph and a
description of a run of the dfs algorithm on this graph:
--- --- ---
| A |---------| B |------| F |
--- /--- ---
| /
| /-----/
| /
---/ --- ---
| C |--------| D |--------| E |
--- --- ---
Suppose we call dfs at the vertex (C) then, the sequence of calls
made is as follows:(Any call to an already visited vertex is
placed inside square parantheses)
dfs(C)
|
|-------> dfs(A)
| |
| |--------> dfs(B)
| | |
| | |-------> [dfs(C)]
| | |-------> [dfs(B)]
| | |-------> dfs(F)
| | |
| | |-------> [dfs(B)]
| |
| |--------> [dfs(C)]
|
|-------> [dfs(B)]
|
|
|-------> dfs(D)
|
|--------> dfs(E)
| |
| |-------> [dfs(D)]
|
|---------> [dfs(C)]
The order in which the vertices are visited is C, A, B, F, D,
E. Starting at the vertex C and having picked the neighbour A,
the dfs visited all the vertices reachable via A (namely A, B,
and F) before returning to explore the graph via the other
neighbour $D$.
Notice, that each dfs(v) is called as many times as there are
edges incident on v. Thus each vertex is examined as many times
as its degree and thus the overall running time is proportional
to the number of edges in G. However, that is true only if we can
examine each neighbour of a vertex in time proportional to its
degree. However, if we maintain the graph as an adjacency matrix
then this algorithm will take time proportional to N*N. Thus the
overall time taken to find the articulation points is N*N*N.
(This will get 100% marks for the range of inputs mentioned in
the problem statement.)
Exercise: Try and write a iterative version of the dfs algorithm
(i.e. try to program it without recursion.) Hint: Recall that
the vertices were maintained in a queue in the BFS
algorithm. Here you would need a "stack". i.e. an array into with
vertices are inserted and removed where the element removed is
the last one to be inserted.
It turns out that a single DFS of the graph G can determine all
the articulation points in the graph! However, we postpone a
description of that idea to a different day.
Copyright (c) IARCS 2003-2024; Last Updated: 17 Jul 2005