You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit (i.e. entry/exit points are unidirectional doors like valves).
The cells are named with an integer value from 0 to N-1.
You have to find:
The sum of the largest sum cycle in the maze. Return -1 if there are no cycles.
Sum of a cycle is the sum of the node number of all nodes in that cycle.
Input Format:
- The first line has the number of cells
N. - The second line has a list of
Nvalues of theedge[]array.edge[i]contains the cell number that can be reached from cell'i'in one step.edge[i]is-1if the'i'th cell doesn't have an exit. Output Format: The first line denotes the sum of the largest sum cycle.
Example 1
Input:
n = 23
edge = [4, 4, 1, 4, 13, 8, 8, 8, 0, 8, 14, 9, 15, 11, -1, 10, 15, 22, 22, 22, 22, 22, 21]Output:
45Explanation: oo
解法
每个节点出度最多 1，是函数图(功能图)。从每个未访问节点沿 edge 走，用三态标记(未访问/在当前路径/已结算)和路径栈定位环：当走到 in-stack 的节点时，从该点到栈顶就是环；累加节点编号作为环和。时间复杂度 O(n)，空间复杂度 O(n)。
from typing import List
def largestSumCycle(n: int, edge: List[int]) -> int:
UNVISITED, ON_STACK, DONE = 0, 1, 2
state = [UNVISITED] * n
pos_in_stack = [-1] * n
best = -1
for start in range(n):
if state[start] != UNVISITED:
continue
path = []
cur = start
while cur != -1 and state[cur] == UNVISITED:
state[cur] = ON_STACK
pos_in_stack[cur] = len(path)
path.append(cur)
cur = edge[cur]
if cur != -1 and state[cur] == ON_STACK:
cycle_start = pos_in_stack[cur]
s = sum(path[cycle_start:])
if s > best:
best = s
for node in path:
state[node] = DONE
return bestclass Solution {
int largestSumCycle(int n, int[] edge) {
int[] state = new int[n];
int[] posInStack = new int[n];
Arrays.fill(posInStack, -1);
long best = -1;
for (int start = 0; start < n; start++) {
if (state[start] != 0) continue;
List<Integer> path = new ArrayList<>();
int cur = start;
while (cur != -1 && state[cur] == 0) {
state[cur] = 1;
posInStack[cur] = path.size();
path.add(cur);
cur = edge[cur];
}
if (cur != -1 && state[cur] == 1) {
long s = 0;
for (int i = posInStack[cur]; i < path.size(); i++) s += path.get(i);
if (s > best) best = s;
}
for (int node : path) state[node] = 2;
}
return (int) best;
}
}class Solution {
public:
int largestSumCycle(int n, vector<int>& edge) {
vector<int> state(n, 0), posInStack(n, -1);
long long best = -1;
for (int start = 0; start < n; start++) {
if (state[start] != 0) continue;
vector<int> path;
int cur = start;
while (cur != -1 && state[cur] == 0) {
state[cur] = 1;
posInStack[cur] = path.size();
path.push_back(cur);
cur = edge[cur];
}
if (cur != -1 && state[cur] == 1) {
long long s = 0;
for (int i = posInStack[cur]; i < (int)path.size(); i++) s += path[i];
if (s > best) best = s;
}
for (int node : path) state[node] = 2;
}
return (int) best;
}
};You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit
(ie. entry/exit points are unidirectional doors like valves).
The cells are named with an integer value from 0 to N-1.
You have to find:
Nearest meeting cell:
Given any two cells - C1, C2, find the closest cell Cm that can be reached from both C1 and C2.
Function Description
You are given a function Solution containing arr[N], src, desc as inputs.
Complete the code in the function and return the answer from it.
Input Format
An integer T, denoting the number of testcases, followed by 3T lines, as each testcase will contain 3 lines.
The first line of each testcase has the number of cells N
The second line of each testcase has a list of N values of the edge[] array. edge[i] contains the cell number that can be reached from cell 'i' in one step. edge[i] is -1 if the i'th cell doesn't have an exit.
Third line for each testcase contains two cell numbers whose nearest meeting cell needs to be found. (return -1 if there is no meeting cell from the two given cells)
Output Format
For each testcase given, output a single line that denotes the nearest meeting cell (NMC)
Example 1
Input:
n = 23
arr = [4, 4, 1, 4, 13, 8, 8, 8, 0, 8, 14, 9, 15, 11, -1, 10, 15, 22, 22, 22, 22, 22, 21]
src = 9
dest = 2Output:
4Explanation: oo
解锁全部 1 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理