Indian Computing Olympiad

Training Material


Advanced Graph Algorithms→One Way Roads

Given a network of intersections and roads, turn all the roads into one-way roads such that every pair of intersections is still connected by a path. If it is possible, give such an orientation, else print NO.

Solution

Observations:

  1. If there is a solution, every pair of vertices must be part of a cycle in the original undirected graph.

    (For every pair of vertices u and v, there is a path from u to v and a path from v to u. Let i→j be a directed edge on the route from u to v. There must be a path that returns from v to u without using this edge.)

  2. Can we use the DFS tree to orient the edges? Orient tree edges down and back edges up. This will work, if the original graph can be oriented.

How do we check, however, if the graph can be oriented. If not, how do we identify the "bad" edges?

Consider an example.

              b
             / \
            /   \
           a     c
            \   / \
             \ /   \
              d-----e
             / \    |
            /   \   |
           i-----j  |
                    f
                   / \
                  /   \
                 g-----h

DFS tree:

    [1]  a..........
         |          .
    [2]  b           .
         |           .
    [3]  c.......... .
         |          ..
    [4]  e---------- .
         |          \.
    [5]  f.     [8]  d.
         | .         | .
    [6]  g .    [9]  i .
         | .         | .
    [7]  h.    [10]  j.
      

Here, if we orient tree edges down and back edges up, we cannot get from {f,g,h} to the rest of the graph.

This is because the edge (e,f) is a "cut-edge" or a bridge. The graph becomes disconnected if (e,f) is deleted.

Observe that low(f) = 5 is strictly greater than DFS_number(e) = 4. It is not difficult to argue that this is a general property of bridges.

A tree edge (u,v) is a bridge iff low(v) > DFS_number(u)

The end points of a bridge will always be cut vertices. However, it is not necessary that an edge joining two cut vertices is always a bridge. For instance:

                /\        /\
               /  \      /  \
               ----x----y----
                   |    |
                   |    |
                    ----
      

Here x and y are cut vertices, but the edge (x,y) is not a bridge.

Example 2:

                                     DFS

    a---------f--------g----i         a1.....
    |       / |        |   /          |      .
    |     /   |        | /          ..b2      .
    |   /     |        h           .  | \     .
    | /       |                    .  c3  e5  .
    b-------- d                    .  |   |  .
    | \                             ..d4  f6.
    |   \                                 |
    c--- d                                g7.
                                          |  .
                                          h8 .
                                          |  .
                                          i9.
      

f-g is critical because low(g) < DFS_number(f)