Leetcode Contest 76 Problem 3 - Find Eventual Safe States

[InthraOnsap]

Thank you so much for pointing out the sentence.
"there exists a natural number K so that for any choice of where to walk, we must have stopped at a terminal node in less than K steps." (The problem's description)
I was confused for many hours.

[shreshthsingh]

life saver, never thought i could find non chinese video.

[martinharris]

Thanks man, super clear explanation. High value channel, instantly subscribed.

[Yash-ukib]

why is 1 not included in the sample ans?? from 1 u can to 2 and then to 5

[mayue]

you can pass visited vertices by reference, at any time in the recursion, the visited vertices are the same, if there's some vertices visited, they will be copied to next recursion call using copy constructor(may be an expensive operation), so we keep track until the starting vertex is done, however, when calling it all over again (at the outer for loop looping over the vertices, ), the visited vertices will be cleared, then you can do
for (int i = 0; i < graph.size(); i++, visited_nodes.clear()) {
if (dfs(graph, i, visited_nodes))
ans.push_back(i);
}


#note: based on the property of a directed graph, it seems to work even when you never clear the visited vertices, but i have no proof. i prefer clear(), it is easier to reason about.

[denisyaroshevskiy]

I don't think it's linear time since you copy unordered_sets.

Why not just push/pop elements? This could work, right?

[SHASHANKRUSTAGII]

Very slow
This code is faster

class Solution {
public:
// topological sorting with dp
bool dfs(vector<vector<int>>& graph, vector<int> &dp, int src) {
if(dp[src])
return 1 == dp[src];

dp[src] = -1; // by default mark it as "cannnot be topologically sorted"
for(auto node : graph[src])
if(false == dfs(graph, dp, node))
return false;
return dp[src] = 1; // next node with zero outdegree
}
vector<int> graph) {
int total_nodes = graph.size();
vector<int> result, dp(total_nodes, 0);
for(int i = 0; i < total_nodes; i++)
if(dfs(graph, dp, i))
result.push_back(i);

return result;
}

};