結果
| 問題 |
No.1776 Love Triangle 2 (Hard)
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:56:18 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,853 bytes |
| コンパイル時間 | 416 ms |
| コンパイル使用メモリ | 82,780 KB |
| 実行使用メモリ | 85,868 KB |
| 最終ジャッジ日時 | 2025-05-14 12:58:47 |
| 合計ジャッジ時間 | 12,734 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 4 TLE * 1 -- * 171 |
ソースコード
import sys
# Increase recursion depth limit for deep searches that might occur with path lengths up to N.
# N can be up to 150. Setting limit to N + buffer, e.g., 200 or higher.
# Using 2000 as a safe large value.
try:
sys.setrecursionlimit(2000)
except Exception as e:
# Some platforms might restrict changing recursion depth. Proceed anyway.
# Might raise RecursionError if path length exceeds default limit.
# print(f"Warning: Could not set recursion depth: {e}", file=sys.stderr)
pass
def solve():
# Read N (number of students) and M (number of friendships)
N, M = map(int, sys.stdin.readline().split())
# Read the three special students X, Y, Z
X, Y, Z = map(int, sys.stdin.readline().split())
# Initialize adjacency matrix for the friendship graph G.
# adj[u][v] = True if u and v are friends.
# Size (N+1)x(N+1) to use 1-based indexing conveniently.
adj = [[False] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
u, v = map(int, sys.stdin.readline().split())
adj[u][v] = True
adj[v][u] = True # Friendships are mutual (undirected graph)
# Precompute the adjacency list for the complement graph G_bar.
# An edge (u, v) exists in G_bar if u and v are NOT friends.
# Store neighbors for each node in a list.
non_friend_adj = [[] for _ in range(N + 1)]
for i in range(1, N + 1):
for j in range(1, N + 1):
# Check if i and j are different nodes and are not friends
if i != j and not adj[i][j]:
non_friend_adj[i].append(j)
# Sort the neighbor lists for G_bar. This is crucial for ensuring that
# when we explore paths, we do so in an order that guarantees finding
# the lexicographically smallest path first.
for i in range(1, N + 1):
non_friend_adj[i].sort()
# Variables to store the result: minimum cycle length k and the path itself.
best_k = -1
best_path = []
# State variables for the Depth First Search (DFS)
visited = [False] * (N + 1) # Keep track of nodes visited in the current path
path = [] # Store the nodes in the current path being explored
# Recursive DFS function to find a cycle of a specific length k_target
def find_cycle_recursive(curr_node, k_target):
# Declare that we intend to modify these variables defined in the outer scope
nonlocal best_k, best_path
# Add the current node to the path and mark it as visited
path.append(curr_node)
visited[curr_node] = True
current_len = len(path)
# Base Case: If the path length reaches the target length k_target
if current_len == k_target:
# Check two conditions for a valid cycle:
# 1. The last node in the path (curr_node) must be able to connect back to the starting node X.
# This means curr_node and X must NOT be friends (edge exists in G_bar).
# 2. The required students Y and Z must be included in the path.
# Check connection back to X
if not adj[curr_node][X]:
# Check inclusion of Y and Z using the visited array (efficient)
if visited[Y] and visited[Z]:
# Found a valid cycle that satisfies all conditions!
best_k = k_target
# Construct the final path representation: start node X, followed by path nodes, ending with X.
# The 'path' list currently contains nodes from X up to curr_node.
# We need to copy it and append X at the end for the output format.
best_path = path[:] + [X]
# Backtrack state correctly before returning True to signal success
visited[curr_node] = False
path.pop()
return True # Cycle found
# If either condition fails (cannot connect back to X, or Y/Z missing), backtrack state
visited[curr_node] = False
path.pop()
return False # Cycle not valid or incomplete, continue search
# Recursive Step: Explore neighbors of the current node
# Iterate through neighbors in the complement graph G_bar
# The neighbors list is already sorted, ensuring lexicographical exploration
for next_node in non_friend_adj[curr_node]:
# Explore neighbor only if it has not been visited in the current path
# This prevents cycles within the path (ensures simple path)
if not visited[next_node]:
# Make the recursive call for the neighbor
if find_cycle_recursive(next_node, k_target):
# If the recursive call returns True, it means a cycle was found down that path.
# We need to propagate this True result upwards.
# Important: Backtrack the state of the current node before returning.
visited[curr_node] = False
path.pop()
return True # Signal cycle found
# If no cycle was found through any neighbor of curr_node, backtrack state
visited[curr_node] = False
path.pop()
return False # No cycle found from this path branch
# Main part of the algorithm: Iterate through possible cycle lengths k
# Start from k=3 (minimum possible cycle length) up to N (maximum possible).
for k in range(3, N + 1):
# Reset the visited array and path list for the search with the new length k
# Clearing the visited array directly is faster than creating a new one each time.
for i in range(1, N + 1):
visited[i] = False
path = [] # Reset the path list
# Start the DFS search from the designated starting node X
if find_cycle_recursive(X, k):
# If find_cycle_recursive returns True, it means a cycle of length k was found.
# Since we iterate k in increasing order, the first k for which we find a cycle is the minimum k.
# And because we explore neighbors in sorted order, the first cycle found for this minimum k
# is guaranteed to be the lexicographically smallest one.
# Therefore, we can stop the search immediately.
break
# After checking all possible lengths k, output the result.
if best_k != -1:
# A valid cycle was found
print(best_k) # Output the minimum length k
print(*(best_path)) # Output the lexicographically smallest path (nodes separated by spaces)
else:
# No valid cycle was found for any length k
print("-1")
# Execute the main function to solve the problem
solve()