Question

PYTHON

The UTM campus is pretty big. There are n buildings scattered around it, numbered from 0 to n-1. These buildings are so far away from each other that the only way to get from one to another is to take a campus bus.

There are m campus bus routes. The i-th one (0 <= i < m) takes you from building u_i to building v_i (but not the other way around). These buses run very frequently.

Professor Zingaro is deciding where to hold his CSC108 lectures. He believes a building x is accessible from a building y if you can get from y to x taking at most two buses. For his students’ convenience, he wants to hold his lectures in the most accessible building. Help him out by telling him how many buildings the most accessible building is accessible from. In addition, list all buildings that are the most accessible.

Filename

Your filename for this question must be q2.py.

Input

The first line of the input contains two space-separated integers n and m, denoting the number of buildings and bus routes, respectively.

m lines follow. The i-th one contains two space-separated integers u_i and v_i, as described above.

Output

The output should consist of two lines. The first line should contain a single integer x denoting the number of buildings that the most accessible building is accessible from

The second line should contain a list of up to n integers, denoting the list of buildings that are accessible from exactly x buildings. List the buildings in increasing order.

Constraints

1 <= n <= 10000

0 <= u_i, v_i < n

u_i != v_i (i.e. no route connects a building to itself)

For any building, there are at most 70 bus routes that end at it.

There are no additional constraints on m or the routes.

Time Limit

Your program must finish running on any valid input within 9 seconds.

Sample Input 1

6 5
0 1
1 2
2 3
3 4
4 5
Sample Output 1

3
2 3 4 5
Sample 1 Explanation

The first line indicates that there are 6 buildings and 5 bus routes.

The bus routes are described in the next 5 lines. For instance, the second route takes you from building 1 to building 2.

Building 0 is only accessible from itself. Building 1 is accessible from building 0 and itself. The remaining buildings are all accessible from 3 buildings, including themselves.

Sample Input 2

6 8
0 1
2 1
1 3
4 3
3 5
0 1
3 0
1 0
Sample Output 2

5
0 3

Answer 1

from collections import deque

def find_most_accessible_buildings(n, m, routes):

# Create an adjacency list to represent the graph

graph = [[] for _ in range(n)]

for u, v in routes:

graph[u].append(v)

# Initialize the lists to keep track of the distances and counts

distances = [-1] * n

counts = [0] * n

# Perform BFS starting from each building

for start in range(n):

visited = [False] * n

queue = deque()

queue.append((start, 0))

visited[start] = True

distances[start] = 0

while queue:

current, distance = queue.popleft()

counts[distance] += 1

for neighbor in graph[current]:

if not visited[neighbor]:

visited[neighbor] = True

queue.append((neighbor, distance + 1))

distances[neighbor] = distance + 1

# Find the maximum count and the buildings with that count

max_count = max(counts)

accessible_buildings = [i for i, count in enumerate(counts) if count == max_count]

return max_count, accessible_buildings

# Read the input

n, m = map(int, input().split())

routes = [tuple(map(int, input().split())) for _ in range(m)]

# Call the function to find the most accessible buildings

max_count, accessible_buildings = find_most_accessible_buildings(n, m, routes)

# Print the output

print(max_count)

print(' '.join(map(str, accessible_buildings)))

Step-by-step explanation:

To solve this problem, we can use graph traversal algorithms like Breadth-First Search (BFS) to find the number of buildings accessible from each building. Here's a Python implementation for this problem:

```python

from collections import deque

def find_most_accessible_buildings(n, m, routes):

# Create an adjacency list to represent the graph

graph = [[] for _ in range(n)]

for u, v in routes:

graph[u].append(v)

# Initialize the lists to keep track of the distances and counts

distances = [-1] * n

counts = [0] * n

# Perform BFS starting from each building

for start in range(n):

visited = [False] * n

queue = deque()

queue.append((start, 0))

visited[start] = True

distances[start] = 0

while queue:

current, distance = queue.popleft()

counts[distance] += 1

for neighbor in graph[current]:

if not visited[neighbor]:

visited[neighbor] = True

queue.append((neighbor, distance + 1))

distances[neighbor] = distance + 1

# Find the maximum count and the buildings with that count

max_count = max(counts)

accessible_buildings = [i for i, count in enumerate(counts) if count == max_count]

return max_count, accessible_buildings

# Read the input

n, m = map(int, input().split())

routes = [tuple(map(int, input().split())) for _ in range(m)]

# Call the function to find the most accessible buildings

max_count, accessible_buildings = find_most_accessible_buildings(n, m, routes)

# Print the output

print(max_count)

print(' '.join(map(str, accessible_buildings)))

```

In this implementation, the function `find_most_accessible_buildings` takes the number of buildings `n`, the number of bus routes `m`, and a list of `routes` as input. It creates an adjacency list `graph` to represent the connections between buildings. It then performs a BFS starting from each building to find the distances and counts of accessible buildings. Finally, it finds the maximum count and the buildings with that count.

In the main part of the code, it reads the input, calls the `find_most_accessible_buildings` function, and prints the output as specified in the problem statement.

You can run this code and provide the input as described in the problem to get the corresponding output.