A Better Battle Plan

Computer Science Level 4

During a battle, Sheldor the conqueror notices that his cities are in the form of a Directed Acyclic Graph, i.e, all the roads are one-way and there is no sequence of roads starting from a city that comes back into it.

Because the roads are one way, Sheldor wants to order them in a fashion which will let him know in which order he should he should progress his troops, i.e, he needs a permutation of the cities such that if there is a road from $u$ to $v$ , $v$ occurs after $u$ in the permutation.

Four of his ministers, Alice, Bob, Charles and David attempt this problem and produce these answers:

Whose answer is correct?

Input File: Link

Input Format and Details:

There are 30 cities numbered from 1 to 30.
Each line of the file contains two integers u v in that order. This means that there is a directed edge from u to v .

Bob David Alice Charles

1 solution

Agnishom Chattopadhyay
Aug 14, 2016

We begin by converting our edge list to a adjacency list.

1
2
3

children = [[] for i in xrange(31)]
for edge in edgeList:
    children[edge[0]].append(edge[1])

Then, it is straightforward to check whether the given permutation is a topological sorting:

def checkTopoSort(perm,children):
    for u in xrange(1,31):
        for v in children[u]:
            if perm.index(v) < perm.index(u):
                return False
    return True

A Better Battle Plan

1 solution

0 pending reports