LeetCode Solutions
enum class State { kInit, kVisiting, kVisited };
class Solution {
public:
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
vector<int> ans;
vector<State> state(graph.size());
for (int i = 0; i < graph.size(); ++i)
if (!hasCycle(graph, i, state))
ans.push_back(i);
return ans;
}
private:
bool hasCycle(const vector<vector<int>>& graph, int u, vector<State>& state) {
if (state[u] == State::kVisiting)
return true;
if (state[u] == State::kVisited)
return false;
state[u] = State::kVisiting;
for (const int v : graph[u])
if (hasCycle(graph, v, state))
return true;
state[u] = State::kVisited;
return false;
}
};
|
enum State { kInit, kVisiting, kVisited }
class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
List<Integer> ans = new ArrayList<>();
State[] state = new State[graph.length];
for (int i = 0; i < graph.length; ++i)
if (!hasCycle(graph, i, state))
ans.add(i);
return ans;
}
private boolean hasCycle(int[][] graph, int u, State[] state) {
if (state[u] == State.kVisiting)
return true;
if (state[u] == State.kVisited)
return false;
state[u] = State.kVisiting;
for (final int v : graph[u])
if (hasCycle(graph, v, state))
return true;
state[u] = State.kVisited;
return false;
}
}
|
from enum import Enum
class State(Enum):
kInit = 0
kVisiting = 1
kVisited = 2
class Solution:
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
state = [State.kInit] * len(graph)
def hasCycle(u: int) -> bool:
if state[u] == State.kVisiting:
return True
if state[u] == State.kVisited:
return False
state[u] = State.kVisiting
if any(hasCycle(v) for v in graph[u]):
return True
state[u] = State.kVisited
return [i for i in range(len(graph)) if not hasCycle(i)]
|
