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
解法
从 src 沿出边走收集每个节点的距离 dSrc[v]；再从 dest 沿出边走，第一个在 dSrc 中出现的节点就是最近交汇点。注意要处理可能的环(用 visited 集合阻止重复进入)。时间复杂度 O(n)，空间复杂度 O(n)。
from typing import List
def nearestMeetingCell(n: int, arr: List[int], src: int, dest: int) -> int:
dSrc = {}
cur, d = src, 0
while cur != -1 and cur not in dSrc:
dSrc[cur] = d
cur = arr[cur]
d += 1
best = -1
best_dist = float('inf')
cur, d = dest, 0
seen = set()
while cur != -1 and cur not in seen:
if cur in dSrc:
total = max(dSrc[cur], d)
if total < best_dist:
best_dist = total
best = cur
break
seen.add(cur)
cur = arr[cur]
d += 1
return bestclass Solution {
int nearestMeetingCell(int n, int[] arr, int src, int dest) {
Map<Integer, Integer> dSrc = new HashMap<>();
int cur = src, d = 0;
while (cur != -1 && !dSrc.containsKey(cur)) {
dSrc.put(cur, d++);
cur = arr[cur];
}
Set<Integer> seen = new HashSet<>();
cur = dest; d = 0;
while (cur != -1 && !seen.contains(cur)) {
if (dSrc.containsKey(cur)) return cur;
seen.add(cur);
cur = arr[cur];
d++;
}
return -1;
}
}class Solution {
public:
int nearestMeetingCell(int n, vector<int>& arr, int src, int dest) {
unordered_map<int, int> dSrc;
int cur = src, d = 0;
while (cur != -1 && !dSrc.count(cur)) {
dSrc[cur] = d++;
cur = arr[cur];
}
unordered_set<int> seen;
cur = dest;
while (cur != -1 && !seen.count(cur)) {
if (dSrc.count(cur)) return cur;
seen.insert(cur);
cur = arr[cur];
}
return -1;
}
};