UVa 610 Street Directions

Problem: convert a all bi-directional street map to a map that contains the same streets but maximum number of one-directional streets. Problem size: 1000 intersections at most, each intersection connects 4 streets at most.

Easy problem. The graph can be stored in an 1000x1000 array. Perform DFS and mark all back edges as a directed edge. In the DFS tree, each edge to a subtree is on a cycle if the subtree has a back edge goes up, and mark such edges directed also. Notice the directions of back edges and tree edges that on a cycle.