| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1257654 | anha3k25cvp | Potemkin cycle (CEOI15_indcyc) | C++20 | 0 ms | 0 KiB |
function solve():
read n, m
adj = adjacency_list[n+1]
has_edge = boolean_matrix[n+1][n+1]
for i from 1 to m:
read u, v
adj[u].push(v)
adj[v].push(u)
has_edge[u][v] = has_edge[v][u] = true
for u from 1 to n:
if adj[u].size() < 2: continue
// Duyệt qua cặp hàng xóm (v, w) của u
for i from 0 to adj[u].size() - 1:
for j from i + 1 to adj[u].size() - 1:
v = adj[u][i]
w = adj[u][j]
// Bỏ qua nếu tạo thành chu trình 3
if has_edge[v][w]:
continue
// Tìm đường đi từ v đến w không qua u bằng BFS
queue q
parent = map
visited = set
q.push(v)
visited.add(u)
visited.add(v)
parent[v] = -1 // Điểm bắt đầu
path_found = false
while not q.empty():
curr = q.front(); q.pop()
if curr == w:
path_found = true
break
for neighbor in adj[curr]:
if neighbor not in visited:
visited.add(neighbor)
parent[neighbor] = curr
q.push(neighbor)
if path_found:
// Dựng lại và in chu trình
path = []
curr = w
while curr != -1:
path.push_back(curr)
curr = parent[curr]
reverse(path.begin(), path.end())
// In kết quả
print(u)
for node in path:
print(node)
return // Tìm thấy, kết thúc
// Không tìm thấy chu trình nào
print("no")