Posts tagged as “graph”

花花酱 LeetCode 815. Bus Routes

By zxi on April 9, 2018

Problem

题目大意：给你每辆公交车的环形路线，问最少需要坐多少辆公交车才能送S到达T。

https://leetcode.com/problems/bus-routes/description/

We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->… forever.

We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.

Example:
Input: 
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
Output: 2
Explanation: 
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Note:

1 <= routes.length <= 500.
1 <= routes[i].length <= 500.
0 <= routes[i][j] < 10 ^ 6.

Solution: BFS

Time Complexity: O(m*n) m: # of buses, n: # of routes

Space complexity: O(m*n + m)

C++

// Author: Huahua

// Running time: 89 ms

class Solution {

public:

int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {

if (S == T) return 0;

unordered_map<int, vector<int>> m;

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

for (const int stop : routes[i])

m[stop].push_back(i);

vector<int> visited(routes.size(), 0);

queue<int> q;

q.push(S);

int buses = 0;

while (!q.empty()) {

int size = q.size();

++buses;

while (size--) {

int curr = q.front(); q.pop();

for (const int bus : m[curr]) {

if (visited[bus]) continue;

visited[bus] = 1;

for (int stop : routes[bus]) {

if (stop == T) return buses;

q.push(stop);

}

return -1;

}

};

花花酱 LeetCode 433. Minimum Genetic Mutation

By zxi on March 24, 2018

Problem

题目大意：给你一个基因库，问一个基因最少需要变异多少次才能变为另外一个基因。每次变异只能修改一个字符，并且必须在基因库里。

https://leetcode.com/problems/minimum-genetic-mutation/description/

A gene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T".

Suppose we need to investigate about a mutation (mutation from “start” to “end”), where ONE mutation is defined as ONE single character changed in the gene string.

For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.

Also, there is a given gene “bank”, which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things – start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from “start” to “end”. If there is no such a mutation, return -1.

Note:

Starting point is assumed to be valid, so it might not be included in the bank.
If multiple mutations are needed, all mutations during in the sequence must be valid.
You may assume start and end string is not the same.

Example 1:

start: "AACCGGTT"
end:   "AACCGGTA"
bank: ["AACCGGTA"]

return: 1

Example 2:

start: "AACCGGTT"
end:   "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

return: 2

Example 3:

start: "AAAAACCC"
end:   "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]

return: 3

Solution: BFS Shortest Path

Time complexity: O(n^2)

Space complexity: O(n)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int minMutation(string start, string end, vector<string>& bank) {

queue<string> q;

q.push(start);

unordered_set<string> visited;

visited.insert(start);

int mutations = 0;

while (!q.empty()) {

size_t size = q.size();

while (size--) {

string curr = std::move(q.front()); q.pop();

if (curr == end) return mutations;

for (const string& gene : bank) {

if (visited.count(gene) || !validMutation(curr, gene)) continue;

visited.insert(gene);

q.push(gene);

}

++mutations;

}

return -1;

}

private:

bool validMutation(const string& s1, const string& s2) {

int count = 0;

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

if (s1[i] != s2[i] && count++) return false;

return true;

}

};

花花酱 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;

}

Posts tagged as “graph”

花花酱 LeetCode 815. Bus Routes

Problem

Solution: BFS

花花酱 LeetCode 433. Minimum Genetic Mutation

Problem

Solution: BFS Shortest Path

花花酱 LeetCode 802. Find Eventual Safe States

Problem

Idea: Finding Cycles

Solution 1: DFS

Related Problems

花花酱 LeetCode 797. All Paths From Source to Target

花花酱 LeetCode 210. Course Schedule II

Problem

Idea

Solution 1: Topological Sorting

C++

Java

Related Problems: