Posts tagged as “directed graph”

花花酱 LeetCode 802. Find Eventual Safe States

By zxi on March 17, 2018

Problem

https://leetcode.com/problems/find-eventual-safe-states/description/

题目大意：给一个有向图，找出所有不可能进入环的节点。

In a directed graph, we start at some node and every turn, walk along a directed edge of the graph. If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.

Now, say our starting node is eventually safe if and only if we must eventually walk to a terminal node. More specifically, 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.

Which nodes are eventually safe? Return them as an array in sorted order.

The directed graph has N nodes with labels 0, 1, ..., N-1, where N is the length of graph. The graph is given in the following form: graph[i] is a list of labels j such that (i, j) is a directed edge of the graph.

Example:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Here is a diagram of the above graph.

Note:

graph will have length at most 10000.
The number of edges in the graph will not exceed 32000.
Each graph[i] will be a sorted list of different integers, chosen within the range [0, graph.length - 1].

Idea: Finding Cycles

Solution 1: DFS

A node is safe if and only if: itself and all of its neighbors do not have any cycles.

Time complexity: O(V + E)

Space complexity: O(V + E)

// Author: Huahua

// Running time: 155 ms

class Solution {

public:

vector<int> eventualSafeNodes(vector<vector<int>>& graph) {

vector<State> states(graph.size(), UNKNOWN);

vector<int> ans;

for (int i = 0; i < graph.size(); ++i)

if (dfs(graph, i, states) == SAFE)

ans.push_back(i);

return ans;

}

private:

enum State {UNKNOWN, VISITING, SAFE, UNSAFE};

State dfs(const vector<vector<int>>& g, int cur, vector<State>& states) {

if (states[cur] == VISITING)

return states[cur] = UNSAFE;

if (states[cur] != UNKNOWN)

return states[cur];

states[cur] = VISITING;

for (int next : g[cur])

if (dfs(g, next, states) == UNSAFE)

return states[cur] = UNSAFE;

return states[cur] = SAFE;

}

};

Problem

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

1	2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

1	4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

题目大意：

给你一些课程和它的先修课程，让你输出修课顺序。如果无法修完所有课程，返回空数组。

Idea

Topological sorting

拓扑排序

Solution 1: Topological Sorting

Time complexity: O(V+E)

Space complexity: O(V+E)

C++

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {

vector<vector<int>> graph(numCourses);

for(const auto& p : prerequisites)

graph[p.second].push_back(p.first);

// states: 0 = unkonwn, 1 == visiting, 2 = visited

vector<int> v(numCourses, 0);

vector<int> ans;

for (int i = 0; i < numCourses; ++i)

if (dfs(i, graph, v, ans)) return {};

std::reverse(ans.begin(), ans.end());

return ans;

}

private:

bool dfs(int cur, vector<vector<int>>& graph, vector<int>& v, vector<int>& ans) {

if (v[cur] == 1) return true;

if (v[cur] == 2) return false;

v[cur] = 1;

for (const int t : graph[cur])

if (dfs(t, graph, v, ans)) return true;

v[cur] = 2;

ans.push_back(cur);

return false;

}

};

Java

// Author: Huahua

// Runtime: 83 ms

class Solution {

public int[] findOrder(int numCourses, int[][] prerequisites) {

ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

for (int i = 0; i < numCourses; ++i)

graph.add(new ArrayList<Integer>());

for (int i = 0; i < prerequisites.length; ++i) {

int course = prerequisites[i][0];

int prerequisite = prerequisites[i][1];

graph.get(course).add(prerequisite);

}

int[] visited = new int[numCourses];

List<Integer> ans = new ArrayList<Integer>();

Integer index = numCourses;

for (int i = 0; i < numCourses; ++i)

if (dfs(i, graph, visited, ans)) return new int[0];

return ans.stream().mapToInt(i->i).toArray();

}

private boolean dfs(int curr, ArrayList<ArrayList<Integer>> graph, int[] visited, List<Integer> ans) {

if (visited[curr] == 1) return true;

if (visited[curr] == 2) return false;

visited[curr] = 1;

for (int next : graph.get(curr))

if (dfs(next, graph, visited, ans)) return true;

visited[curr] = 2;

ans.add(curr);

return false;

}

Solution 1: Topological Sort

C++

// Author: Huahua

// Time complexity: O(n)

// Runtime: 12 ms

class Solution {

public:

bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {

graph_ = vector<vector<int>>(numCourses);

for(const auto& p : prerequisites)

graph_[p.first].push_back(p.second);

// states: 0 = unkonwn, 1 == visiting, 2 = visited

vector<int> v(numCourses, 0);

for(int i = 0; i < numCourses; ++i)

if(dfs(i, v)) return false;

return true;

}

private:

vector<vector<int>> graph_;

bool dfs(int cur, vector<int>& v) {

if(v[cur] == 1) return true;

if(v[cur] == 2) return false;

v[cur] = 1;

for(const int t : graph_[cur])

if(dfs(t, v)) return true;

v[cur] = 2;

return false;

}

};

Java

// Author: Huahua

// Runtime: 6 ms

// HashMap is slower than ArrayList in this problem.

class Solution {

public boolean canFinish(int numCourses, int[][] prerequisites) {

ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

for (int i = 0; i < numCourses; ++i)

graph.add(new ArrayList<Integer>());

for (int i = 0; i < prerequisites.length; ++i) {

int course = prerequisites[i][0];

int prerequisite = prerequisites[i][1];

graph.get(course).add(prerequisite);

}

int[] visited = new int[numCourses];

for (int i = 0; i < numCourses; ++i)

if (dfs(i, graph, visited)) return false;

return true;

}

private boolean dfs(int curr, ArrayList<ArrayList<Integer>> graph, int[] visited) {

if (visited[curr] == 1) return true;

if (visited[curr] == 2) return false;

visited[curr] = 1;

for (int next : graph.get(curr))

if (dfs(next, graph, visited)) return true;

visited[curr] = 2;

return false;

}

Solution 2: DFS Finding cycles

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Time complexity: O(n^2)

// Runtime: 179 ms

class Solution {

public:

bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {

graph_.clear();

for(const auto& p : prerequisites)

graph_[p.first].insert(p.second);

for (int i = 0; i < numCourses; ++i) {

vector<int> visited(numCourses, 0);

if (cycle(i, i, visited)) return false;

}

return true;

}

private:

unordered_map<int, unordered_set<int>> graph_;

bool cycle(int start, int curr, vector<int>& visited) {

if (curr == start && visited[start]) return true;

if (!graph_.count(curr)) return false;

for (const int next : graph_.at(curr)) {

if (visited[next]) continue;

visited[next] = true;

if (cycle(start, next, visited)) return true;

}

return false;

}

};

Related Pr0blems:

花花酱 LeetCode 685. Redundant Connection II

By zxi on October 7, 2017

Problem:

In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, …, N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] that represents a directed edge connecting nodes u and v, where u is a parent of child v.

Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.

Example 1:

Input: [[1,2], [1,3], [2,3]]

Output: [2,3]

Explanation: The given directed graph will be like this:

/ \

v v

2-->3

Example 2:

Input: [[1,2], [2,3], [3,4], [4,1], [1,5]]

Output: [4,1]

Explanation: The given directed graph will be like this:

5 <- 1 -> 2

^ |

| v

4 <- 3

Note:

The size of the input 2D-array will be between 3 and 1000.
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

Idea:

Union Find

Time complexity: O(nlog*n) ~ O(n)

Space complexity: O(n)

Solution:

C++

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {

vector<int> parents(edges.size() + 1, 0);

vector<int> roots(edges.size() + 1, 0);

vector<int> sizes(edges.size() + 1, 1);

vector<int> ans1;

vector<int> ans2;

for(auto& edge: edges) {

int u = edge[0];

int v = edge[1];

// A node has two parents

if (parents[v] > 0) {

ans1 = {parents[v], v};

ans2 = edge;

// Delete the later edge

edge[0] = edge[1] = -1;

}

parents[v] = u;

}

for(const auto& edge: edges) {

int u = edge[0];

int v = edge[1];

// Invalid edge (we deleted in step 1)

if (u < 0 || v < 0) continue;

if (!roots[u]) roots[u] = u;

if (!roots[v]) roots[v] = v;

int pu = find(u, roots);

int pv = find(v, roots);

// Both u and v are already in the tree

if (pu == pv)

return ans1.empty() ? edge : ans1;

// Unoin, always merge smaller set (pv) to larger set (pu)

if (sizes[pv] > sizes[pu])

swap(pu, pv);

roots[pv] = pu;

sizes[pu] += sizes[pv];

}

return ans2;

}

private:

int find(int node, vector<int>& roots) {

while (roots[node] != node) {

roots[node] = roots[roots[node]];

node = roots[node];

}

return node;

}

};

C++ / without using Union find

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {

vector<int> parents(edges.size() + 1, 0);

vector<int> ans1;

vector<int> ans2;

bool dup_parents = false;

for(auto& edge: edges) {

int u = edge[0];

int v = edge[1];

// A node has two parents

if (parents[v] > 0) {

ans1 = {parents[v], v};

ans2 = edge;

dup_parents = true;

// Delete the later edge

edge[0] = edge[1] = -1;

} else {

parents[v] = u;

}

// Reset parents

parents = vector<int>(edges.size() + 1, 0);

for(const auto& edge: edges) {

int u = edge[0];

int v = edge[1];

// Invalid edge (we deleted in step 1)

if (u < 0 || v < 0) continue;

parents[v] = u;

if (cycle(v, parents))

return dup_parents ? ans1 : edge;

}

return ans2;

}

private:

bool cycle(int v, const vector<int>& parents) {

int u = parents[v];

while (u) {

if (u == v) return true;

u = parents[u];

}

return false;

}

};

Python

"""

Author: Huahua

Runtime: 62 ms

"""

class Solution:

def findRedundantDirectedConnection(self, edges):

def cycle(v, p):

u = p[v]

while u != 0:

if u == v: return True

u = p[u]

return False

n = len(edges)

p = [0] * (n + 1)

ans1 = []

ans2 = []

dup_p = False

for e in edges:

u, v = e

if p[v] > 0:

ans1 = [p[v], v]

ans2 = [u, v]

dup_p = True

e[0] = e[1] = -1

else:

p[v] = u

p = [0] * (n + 1)

for u, v in edges:

if u < 0: continue

p[v] = u

if cycle(v, p):

return ans1 if dup_p else [u, v]

return ans2

Posts tagged as “directed graph”

花花酱 LeetCode 802. Find Eventual Safe States

Problem

Idea: Finding Cycles

Solution 1: DFS

Related Problems

花花酱 LeetCode 210. Course Schedule II

Problem

Idea

Solution 1: Topological Sorting

C++

Java

Related Problems:

花花酱 LeetCode 207. Course Schedule

Solution 1: Topological Sort

C++

Java

Solution 2: DFS Finding cycles

C++

Related Pr0blems:

花花酱 LeetCode 685. Redundant Connection II