// Created for this challenge: // https://www.sololearn.com/post/45097 // PRESIDENTIAL CAMPAIGN // Absurdistan is a weird country. It consists of N cities and between some of them there are one-way roads. Since it is possible to use the roads only in one direction, it might be impossible to travel from some cities to other. // The elections are coming and the president is doing a campaign to get elected again. He would like to give speeches to persuade voters in some cities, but he wants to get back to his palace after that. He would like to know the cities for which it is possible to travel both there and back using only the roads in the allowed direction. (He doesn't have a plane yet.) // Let's number the cities from 1 to N. The president lives in the city number 1. // The input contains integers N and M giving the number of cities and roads in Absurdistan. Each of the following M lines contains 2 integers a, b meaning that there is a directed road from city a to city b. // Output the numbers of cities where the president can give a speech that means he can get both there and back using roads // EXAMPLES: // Input: // 5 6 // 1 2 // 1 5 // 5 1 // 3 1 // 3 4 // 4 2 // Output: // 1 5 // It is not possible to get from city 1 to cities 3, 4 and it is not possible to get from city 2 to 1. // +-3-+ // v v // 4 1<->5 // | | // +>2<+ // Input: // 7 10 // 1 2 // 2 3 // 3 4 // 4 1 // 4 2 // 1 5 // 4 6 // 5 7 // 7 6 // 6 5 // 7--+ // ^ v // 5<-6 // ^ ^ // 1<-4<-+ // | v | // +->2->3 // Output: // 1 2 3 4 // Class for the city maintaining it's number and a // list of roads leaving the city. class City(val id: Int) { val roads = mutableListOf() // Method to add a road to the destination. fun connect(destination: City) { roads.add(destination) } // connect } // City // Class for processing the set of cities and roads. // Maintaining the number of cities and their class // instances. class Process(val number: Int, roads: Array>) { val cities = Array(number) {City(it+1)} val visited = Array(number) {false} // 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 traveling from city 1 to others // and back. fun travel() { // List of city numbers processed and if any // path was found. val order = mutableListOf() var found = false // 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, note // that we found a path and state each // city in the path can be reached. if (city.id == 1 || visited[city.id-1]) { found = true 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 // Process the cities. If no paths were found, // state that. tryIt(cities[0]) if (!found) println("No roads found.") // Otherwise, repeat processing cities until // all possible are found and list the cities // we can reach. else { // Initialize the count. Repeat saving the // count, processing the cities, count the // cities visited until the count didn't // change. var count = 0 do { val old = count tryIt(cities[0]) count = visited.count { it } } while (count != old) // List the visited cities. print("Cities:") for (index in 0 until number) if (visited[index]) print(" ${index+1}") println() } // if } // travel // 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. fun first() { 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.travel() } // first // Function to process the second example of the // challenge. fun second() { 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.travel() } // second // Function to show a no paths example. fun third() { val process = Process(3, arrayOf(arrayOf(1, 2), arrayOf(1, 3), arrayOf(2, 3))) process.display() process.travel() } // third // Function to show multiple valid paths example. fun fourth() { val process = Process(3, arrayOf(arrayOf(1, 2), arrayOf(2, 1), arrayOf(1, 3), arrayOf(3, 1), arrayOf(3, 2))) process.display() process.travel() } // fourth // 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.travel() // 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() } // try } // main

president ch