Diocletian - Part 2
My code-
cook your dish here
def generate_reasonable_plans(n, m, p, train_lines):
# Create an adjacency list to represent the graph
graph = [ for _ in range(n)]
for u, v in train_lines:
graph[u - 1].append(v - 1)
graph[v - 1].append(u - 1)
plans = [] # List to store the generated plans
visited = [False] * n # Keep track of visited cities during DFS
def dfs(city, plan):
visited[city] = True
plan.append(str(city % 2)) # Assign cities alternately to Alfa (0) and Bravo (1)
for neighbor in graph[city]:
if not visited[neighbor]:
dfs(neighbor, plan)
# Generate at least p distinct reasonable plans
for _ in range(p):
plan = [] # List to store the current plan
dfs(0, plan) # Start DFS from city 1 (index 0)
# Check if both Alfa and Bravo are connected
if False not in visited:
plans.append(''.join(plan))
# Reset visited list for the next plan
visited = [False] * n
return plans
Read input
n, m, p = map(int, input().split())
train_lines =
for _ in range(m):
u, v = map(int, input().split())
train_lines.append((u, v))
Generate reasonable plans
plans = generate_reasonable_plans(n, m, p, train_lines)
Output the results
print(len(plans))
for plan in plans:
print(plan)