// Created for this challenge: // https://www.sololearn.com/post/46479 // ROADS IN ABSURDISTAN // After getting successfully elected again, the // president of Absurdistan decided to make the // traffic system less absurd. To remind you, // Absurdistan consists of N cities connected by M // one-way roads. The president would like to make // some of the roads two-way so that it will be // possible to travel between any pair of cities // in any direction. However, making a road two-way // is not cheap. Therefore, it is needed to turn the // least possible number of roads into bidirectional. // You are given the description of Absurdistan: // Two integers N and M - the number of cities and // roads. M lines follow, each contains two integers // a and b meaning that there is a one-way road from // city number a to city number b. The cities are // numbered 1 to N. Your task is to find the minimum // number of roads which have to be made two-way so // that it's possible to travel from any city to any // other city using the roads in the allowed // direction(s) or to output that it is impossible. // Bonus: Find a plan which roads to make two-way. // EXAMPLES (WITH PLANS): // Input: // 4 4 // 1 2 // 1 3 // 2 4 // 3 4 // Output: // 2 // 1 2 // 2 4 // This is not the only solution with 2 roads. // Input: // 3 2 // 1 2 // 2 3 // Output: // 2 // 1 2 // 2 3 // Input: // 5 6 // 1 2 // 2 1 // 2 3 // 3 4 // 3 5 // 4 2 // Output: // 1 // 3 5 // Input: // 4 2 // 1 2 // 4 3 // Output: // Impossible // Class for the city maintaining it's number, a // list of roads leaving the city, and list of roads // (paths) arriving at the city. class City(val id: Int) { val roads = mutableListOf() val paths = mutableListOf() // Method to add a road to the destination. fun connect(destination: City) { roads.add(destination) destination.paths.add(this) } // connect // Method to remove a road to the destination. fun disconnect(destination: City) { roads.remove(destination) destination.paths.remove(this) } // disconnect } // City // Class for processing the set of cities and roads. // Maintaining the number of cities and their class // instances. class Process( private val number: Int, roads: Array>) { private val cities = Array(number) { City(it+1) } // Constructor initialization to add the roads // to the cities as needed. init { for (road in roads) cities[road[0]-1].connect(cities[road[1]-1]) } // init // Method to try adding roads to make all cities // accessible. Declare a list of roads made two // way, a saved version so we can compare the // differences, and the list of two ways removed // so we can put them at the start of the list // for the attempt. fun add() { val added = mutableListOf>() val roads = mutableListOf>() // Function to create a list of all roads to // make two way followed by making them two way. fun create() { for (city in cities) for (road in city.roads) if (city !in cities[road.id-1].roads) added.add(arrayOf(city.id, road.id)) for (add in added) cities[add[1]-1].connect(cities[add[0]-1]) } // create // Function to test if all cities are reachable // with the existing roads. Maintain a list // of reachable roads and the cities in our // current path. fun test(): Boolean { val visited = Array(number) { false } val order = mutableListOf() // Recursive function to process a city. fun tryIt(city: City) { // If this city has already been processed, // if it is the first city or a city known to // get back there, this path is valid. // Otherwise, we got a dead end so give up. if (city.id in order) { // If we got back to the first city or a // city known to get back there, state // each city in the path can be reached. if (city.id == 1 || visited[city.id-1]) { for (value in order) visited[value-1] = true } // if // Otherwise, found a new city so add it to // the path, for each road out of this city, // recurse with the destination city, and, // once done, remove the city from the path. } else { order.add(city.id) for (road in city.roads) tryIt(road) order.remove(city.id) } // if } // tryIt // Default the count to none and repeat: // save the old count, try all paths, count // how many cities are reachable now, until // all are reachable or the saved number // matches the current so we can never reach // them all. Return whether we can reach // them all. var count = 0 do { val old = count tryIt(cities[0]) count = visited.count { it } } while (count != number && old != count) return count == number } // test // Function to list the number of roads updated // to two way and list them. fun list() { println("Updated: ${added.size}") for (add in added) println("${add[0]} ${add[1]}") } // list // Function to remove all of the added cities // now that we know there is a winning // combination moving them to our roads to play // with. fun remove() { for (add in added) { cities[add[1]-1].disconnect(cities[add[0]-1]) roads.add(add) } // for added.clear() } // remove // Function to update the roads to two way // connecting all of the cities. Maintain a list // of reachable roads and the cities in our // current path. fun update() { val visited = Array(number) { false } val order = mutableListOf() // Function to follow them to see if a better // answer exists. fun follow(city: City) { println("Following: ${city.id}") } // follow // Recursive function to process a city. fun tryIt(city: City) { // If this city has already been processed, // if it is the first city or a city known to // get back there, this path is valid. // Otherwise, we got a dead end so give up. if (city.id in order) { // If we got back to the first city or a // city known to get back there, state // each city in the path can be reached. if (city.id == 1 || visited[city.id-1]) { for (value in order) visited[value-1] = true } // if // Otherwise, found a new city so add it to // the path, for each road out of this city, // recurse with the destination city, and, // once done, remove the city from the path. } else { order.add(city.id) for (road in city.roads) tryIt(road) order.remove(city.id) } // if } // tryIt // Function to test if all cities are reachable // with the existing roads. Maintain a list // of reachable roads and the cities in our // current path. fun trying(): Int { // Reset the visited state for the next // usage. Default the count to none and // repeat: save the old count, try all paths, // count how many cities are reachable now, // until all are reachable or the saved // number matches the current so we can never // reach them all. Return whether we can // reach them all. for (index in visited.indices) visited[index] = false var count = 0 do { val old = count tryIt(cities[0]) count = visited.count { it } } while (count != number && old != count) return count } // trying // Count the cities that can be reached by both // ends of the road. fun paths(road: Array) = cities[road[0]-1].roads.size+ cities[road[1]-1].roads.size // Function to pick the city with the most // road in or out of it. fun pick(): City { val map = Array(number) { Pair( cities[it].roads.size, cities[it].paths.size) } var max = 0 var id = 0 for (index in 0 until number) { val (road, path) = map[index] if (road > max) { max = road id = index } // if if (path > max) { max = path id = index } // if } // for return cities[id] } // pick // Function to search for the most promising // path. fun search() { // Default the maximum number of cities that // can currently be visited and the road that // became two way to get us there. For each // road that can become two way, find the // best choice. var max = 0 var highest = roads[0] for (index in roads.indices) { // Get the current road, connect the two // way road, count how many cities are // now connectible, if the count is a new // maximum, save it (both count & city), // otherwise, if the count matches the // maximum and the new road yields more // cities, switch to it, and in all cases // disconnect the road. val road = roads[index] cities[road[1]-1].connect( cities[road[0]-1]) val count = trying() if (count > max) { max = count highest = road } else if (count > 0 && count == max && paths(highest) < paths(road)) highest = road cities[road[1]-1].disconnect( cities[road[0]-1]) } // for // Remove the selected road from the possible // two way roads, add it the the list of // roads we have added, and connect the // cities involved. roads.remove(highest) added.add(highest) cities[highest[1]-1].connect( cities[highest[0]-1]) } // search // Function to verify that everything is needed // since it is suspect. fun verify() { // Check to see if any road isn't needed any // more. Starting at the end for each added // road, disconnect it, test to see if it // was needed, if not, remove it from the // list, and otherwise, reconnect it. for (index in added.size-1 downTo 0) { val add = added[index] cities[add[1]-1].disconnect( cities[add[0]-1]) if (test()) added.remove(add) else cities[add[1]-1].connect( cities[add[0]-1]) } // for } // verify // While all the cities are not connected via // roads, search for the next one to connect. while (trying() != number) search() // If there are too many roads, verify they are // needed. if (added.size > 2) verify() // If there are still too many roads, // disconnect the added ones, pick the city // with the most roads in or out, follow them // to see if a better answer exists, and // reconnect the added ones. if (added.size > 2) { for (add in added) cities[add[1]-1].disconnect( cities[add[0]-1]) follow(pick()) for (add in added) cities[add[1]-1].connect( cities[add[0]-1]) } // if } // update // Create a list of all roads that could be made // two way and make them two way. If all cities // can be reached, remove them all before trying // to figure out what ones are needed and listing // the result. create() if (test()) { remove() update() list() // Otherwise, this version of the cities & // roads can not become a winning version. } else println("Impossible") } // add // Method to display the cities and the roads out // of them. fun display() { // For each city, display it's roads. for (city in cities) { print("City ${city.id} with roads to:") // For each road, display it's destination // city identifier. for (road in city.roads) print(" ${road.id}") println() } // for } // display } // Process // Main function to process the cities and roads. fun main(args: Array) { // Function to process the first example of the // challenge. Two roads become two way 1 3 & 3 4 // or 1 2 & 2 4. fun first() { val process = Process(4, arrayOf(arrayOf(1, 2), arrayOf(1, 3), arrayOf(2, 4), arrayOf(3, 4))) process.display() process.add() } // first // Function to process the second example of the // challenge. Two roads become two way 1 2 and 2 3. fun second() { val process = Process(3, arrayOf(arrayOf(1, 2), arrayOf(2, 3))) process.display() process.add() } // second // Function to process the third example of the // challenge. One road becomes two way 3 5. fun third() { val process = Process(5, arrayOf(arrayOf(1, 2), arrayOf(2, 1), arrayOf(2, 3), arrayOf(3, 4), arrayOf(3, 5), arrayOf(4, 2))) process.display() process.add() } // third // Function to process the fourth example of the // challenge. This one is impossible. fun fourth() { val process = Process(4, arrayOf(arrayOf(1, 2), arrayOf(4, 3))) process.display() process.add() } // fourth // Function to process the first example of the // challenge. Two roads become two way 3 4 & 4 2 // or 1 2 & 3 1. fun fifth() { val process = Process(5, arrayOf(arrayOf(1, 2), arrayOf(1, 5), arrayOf(5, 1), arrayOf(3, 1), arrayOf(3, 4), arrayOf(4, 2))) process.display() process.add() } // fifth // Function to process the second example of the // challenge. One road becomes two way 4 6 or 1 5. fun sixth() { val process = Process(7, arrayOf(arrayOf(1, 2), arrayOf(2, 3), arrayOf(3, 4), arrayOf(4, 1), arrayOf(4, 2), arrayOf(1, 5), arrayOf(4, 6), arrayOf(5, 7), arrayOf(7, 6), arrayOf(6, 5))) process.display() process.add() } // sixth // Function to show multiple valid paths example. // Good as it is. fun seventh() { val process = Process(3, arrayOf(arrayOf(1, 2), arrayOf(2, 1), arrayOf(1, 3), arrayOf(3, 1), arrayOf(3, 2))) process.display() process.add() } // seventh // Function that gave wrong answer originally. One // road becomes two way 4 1. fun eight() { val process = Process(4, arrayOf(arrayOf(4, 3), arrayOf(3, 2), arrayOf(2, 1), arrayOf(4, 1))) process.display() process.add() } // eight // Function with same data as eight that gave right // answer. One road becomes two way 4 1. fun nine() { val process = Process(4, arrayOf(arrayOf(4, 1), arrayOf(2, 1), arrayOf(3, 2), arrayOf(4, 3))) process.display() process.add() } // nine // Function that gave wrong data originally. Two // roads become two way 5 6 and 6 4. fun ten() { val process = Process(6, arrayOf(arrayOf(1, 2), arrayOf(2, 3), arrayOf(3, 4), arrayOf(5, 6), arrayOf(6, 4), arrayOf(5, 1))) process.display() process.add() } // ten // Function that gave wrong data originally. Two // roads become two way 8 6 & 9 7 or 8 6 & 9 5. fun eleven() { val process = Process(9, arrayOf(arrayOf(4, 2), arrayOf(6, 2), arrayOf(3, 6), arrayOf(8, 6), arrayOf(1, 9), arrayOf(9, 3), arrayOf(7, 5), arrayOf(9, 7), arrayOf(1, 4), arrayOf(2, 7), arrayOf(5, 2), arrayOf(9, 5), arrayOf(9, 4), arrayOf(9, 1))) process.display() process.add() } // eleven // Try reading the user's inputs to process their // request. try { // Read the line, split into words, convert to // integers, and verify two were given & legal. // If so, process the roads. val inputs = readLine()!!.split(" ").map { it.toInt() } if (inputs.size == 2 && inputs[0] > 1 && inputs[1] >= 0) { // Allocate the array to hold the roads. For // each road, read it, verify it, and store it // in the array. val array = Array(inputs[1]) { Array(2) { 0 } } for (index in 0 until inputs[1]) { // Read the line, split into words, convert // to integers, and verify two were given & // legal. If not, throw an exception. // Otherwise, store the source and // destination into the array. val list = readLine()!!.split(" ").map { it.toInt() } if (list.size != 2 || list[0] !in 1..inputs[0] || list[1] !in 1..inputs[0]) throw IllegalArgumentException( "Bad road inputs!") array[index][0] = list[0] array[index][1] = list[1] } // for // Create the process class instance, display // it's data, and process it's roads. val process = Process(inputs[0], array) process.display() process.add() // Otherwise, inputs were invalid so throw an // exception. } else throw IllegalArgumentException( "Bad city inputs!") // On exception, complain and process the default // examples. } catch (error: Throwable) { println("Bad inputs, using defaults!") first() second() third() fourth() fifth() sixth() seventh() eight() nine() ten() eleven() } // try } // main

roads ch