I participated in Codeforces online contest yesterday and was trying to solve this problemusing DFS (Depth-First-Search). I got somehow stuck in the WA3 (Wrong Answer Test 3). I checked carefully again and again but sadly I couldn’t figure out why.
The connectivity graph is represented using adjacent list, not matrix, because the number of nodes is large and it will cause memory limit error. I use the following two dimensional array of list in Python but at first I didn’t get it right, as one of the common mistakes that beginners might make.
arr = [[]] * n
Instead of real two-dimensional array of elements, it is producing the array of identical-referenced element. The below is the correct way to do it, by using a loop inside the list creation. The sample principle applies to multi-dimensional array creation in Python.
arr = [[] for _ in xrange(n)]
The below quickly illustrates the difference.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Codeforces: B. Roma and Changing Signs
Next Post: Codeforces: A. Beautiful Matrix
For the adjacent list to represent the map I use a dict like this:
{1: [2, 3, 4], 2: [1, 3, 4], 3: [4, 1, 2], 4: [3, 1, 2]}
For this you can just define map like this
map = dict() and construct the map by mapping each int element to a list(the node that can be reached from this int) when reading input.
python genetaor.