You started as a software developer in the Uber company. In this company, a special ride...

 

Transcribed Image Text:

You started as a software developer in the Uber company. In this company, a special ride network is created every day. And your first task is to prove whether you can keep this company's ride network in a tree structure. But the developer who left the company before you has already designed this network using a directed graph. Your task is to measure whether this directed graph can be a tree. After some research, you found that for a directed graph to be a tree, it must have one less number of edges than the number of vertices, it must be connected, and there must be no cycles in the graph. Now prove to your team leader that you can solve this problem. Note: Here you must use the symbol chart data structure when retrieving taxi pickups from the user. Sample Input: Enter the number of taxi pickups: 4 Enter the number of taxi rides: 5 Enter the taxi rides: Cayyolu Emek Emek Kızılay Emek Yenimahalle Kızılay Cayyolu Yenimahalle Kızılay The person who will use your program must first enter the number of taxi pickups in the ride network. Then it should enter how many taxi rides there are connecting these taxi pickups. Finally, it should specify line by line from which taxi pickup to which one can go. For example, in the first line, it is stated that there is a one-way departure from Çayyolu to Emek. Sample Output: Cayyolu: Emek Emek: Yenimahalle Kızılay Kızılay: Cayyolu Yenimahalle: Kızılay This ride network cannot be kept in a tree structure. In the program output, show the user to which taxi pickups a taxi in this ride network can go from its location. For example, in line 1, it is stated that there are only departures from Çayyolu to Emek. And in the last line, print the information on whether this ride mesh can be kept in a tree structure. You started as a software developer in the Uber company. In this company, a special ride network is created every day. And your first task is to prove whether you can keep this company's ride network in a tree structure. But the developer who left the company before you has already designed this network using a directed graph. Your task is to measure whether this directed graph can be a tree. After some research, you found that for a directed graph to be a tree, it must have one less number of edges than the number of vertices, it must be connected, and there must be no cycles in the graph. Now prove to your team leader that you can solve this problem. Note: Here you must use the symbol chart data structure when retrieving taxi pickups from the user. Sample Input: Enter the number of taxi pickups: 4 Enter the number of taxi rides: 5 Enter the taxi rides: Cayyolu Emek Emek Kızılay Emek Yenimahalle Kızılay Cayyolu Yenimahalle Kızılay The person who will use your program must first enter the number of taxi pickups in the ride network. Then it should enter how many taxi rides there are connecting these taxi pickups. Finally, it should specify line by line from which taxi pickup to which one can go. For example, in the first line, it is stated that there is a one-way departure from Çayyolu to Emek. Sample Output: Cayyolu: Emek Emek: Yenimahalle Kızılay Kızılay: Cayyolu Yenimahalle: Kızılay This ride network cannot be kept in a tree structure. In the program output, show the user to which taxi pickups a taxi in this ride network can go from its location. For example, in line 1, it is stated that there are only departures from Çayyolu to Emek. And in the last line, print the information on whether this ride mesh can be kept in a tree structure.

Answer rating: 100% (QA)

from collections import defaultdict def istreegraph numvertices lengraph numedges su... View the full answer