Graph
Last updated
Was this helpful?
Last updated
Was this helpful?
class Solution {
public int[][] updateMatrix(int[][] mat) {
return bfs(mat);
}
private int[][] bfs(int[][] mat) {
int r = mat.length, c = mat[0].length;
Queue<int[]> q = new ArrayDeque<>();
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (mat[i][j] == 0)
q.offer(new int[] {i, j});
else
mat[i][j] = -1;
}
}
int[] directions = new int[] {-1, 0, 1, 0, -1};
while(q.size() > 0) {
int[] curr = q.poll();
int m = curr[0], n = curr[1];
for (int k = 0; k < 4; k++) {
int nm = m + directions[k], nn = n + directions[k+1];
if (nm < 0 || nm == r || nn < 0 || nn == c || mat[nm][nn] != -1)
continue;
mat[nm][nn] = mat[m][n] + 1;
q.offer(new int[] {nm, nn});
}
}
return mat;
}
private int[][] dp(int[][] mat) {
int r = mat.length, c = mat[0].length, INF = r + c;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (mat[i][j] == 0) continue;
int top = INF, left = INF;
if (i - 1 >= 0) top = mat[i - 1][j];
if (j - 1 >= 0) left = mat[i][j - 1];
mat[i][j] = Math.min(top, left) + 1;
}
}
for (int i = r - 1; i >= 0; i--) {
for (int j = c - 1; j >= 0; j--) {
if (mat[i][j] == 0) continue;
int bottom = INF, right = INF;
if (i + 1 < r) bottom = mat[i + 1][j];
if (j + 1 < c) right = mat[i][j + 1];
mat[i][j] = Math.min(mat[i][j], Math.min(bottom, right) + 1);
}
}
return mat;
}
}/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {
val = 0;
neighbors = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList<Node>();
}
public Node(int _val, ArrayList<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
*/
class Solution {
public Node cloneGraph(Node node) {
if (node == null)
return null;
if (node.neighbors.size() == 0)
return new Node(node.val);
return dfs(node, new HashMap<>());
}
private Node dfs(Node cur, Map<Node, Node> map) {
Node clone = new Node(cur.val);
map.put(cur, clone);
for (Node n : cur.neighbors) {
if (map.get(n) != null) {
clone.neighbors.add(map.get(n));
} else {
clone.neighbors.add(dfs(n, map));
}
}
return clone;
}
}import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;
class CourseSchedule {
public boolean canFinish(int numCourses, int[][] prerequisites) {
final int[] courseDeps = new int[numCourses];
for (final int[] pre : prerequisites) {
courseDeps[pre[0]]++;
}
final Set<Integer> zeroDeps = new HashSet<>();
for (int i = 0; i < numCourses; i++) {
if (courseDeps[i] == 0) {
zeroDeps.add(i);
}
}
if (zeroDeps.isEmpty()) {
return false;
}
while(!zeroDeps.isEmpty()) {
final Iterator<Integer> it = zeroDeps.iterator();
final int course = it.next();
zeroDeps.remove(course);
for (final int[] pre : prerequisites) {
if (pre[1] == course) {
courseDeps[pre[0]]--;
if (courseDeps[pre[0]] == 0) {
zeroDeps.add(pre[0]);
}
}
}
}
for (final int i : courseDeps) {
if (i > 0) {
return false;
}
}
return true;
}
@Test
void givenInput1_whenCallCanFinish_thenItShouldReturnTrue() {
final int numCourses = 2;
final int[][] prerequisites = new int[][]{{1, 0}};
assertTrue(canFinish(numCourses, prerequisites));
}
@Test
void givenInput2_whenCallCanFinish_thenItShouldReturnFalse() {
final int numCourses = 2;
final int[][] prerequisites = new int[][]{{1, 0}, {0, 1}};
assertFalse(canFinish(numCourses, prerequisites));
}
}union search / disjoint set / BFS
DFS / recursive
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty())
return 0;
int height = grid.size();
int width = grid[0].size();
int count = 0;
queue<pair<int, int>> q;
vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int r = 0; r < height; r++) {
for (int c = 0; c < width; c++) {
if (grid[r][c] == '1') {
count++;
q.push({r, c});
while(!q.empty()) {
pair<int, int> p = q.front();
q.pop();
if (grid[p.first][p.second] == '0')
// it might have been updated to 0 by other neighbors
continue;
grid[p.first][p.second] = '0';
for (auto& dir : directions) {
int x = p.first + dir.first;
int y = p.second + dir.second;
if (x >= 0
&& x < height
&& y >= 0
&& y < width
&& grid[x][y] == '1') {
q.push({x, y});
}
}
}
}
}
}
return count;
}
};Note that in Graph BFS, compared with Tree BFS, we need to mark the visited node as visited to prevent infinite loop.
// https://leetcode.com/problems/rotting-oranges/
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> visited = grid;
queue<pair<int, int>> q;
int countFreshOrange = 0;
for (int i = 0; i < m; i++) {
for (int j =0; j < n; j++) {
if (visited[i][j] == 2) {
q.push({i, j});
}
if (visited[i][j] == 1) {
countFreshOrange++;
}
}
}
//q.empty() means there is no rotten orange in the grid and countFreshOrange = 0 means we will rotten the freshoranges in 0 mins
if (countFreshOrange == 0)
return 0;
if (q.empty())
return -1;
int minutes = -1;
int directions[] = {-1, 0, 1, 0, -1};
while(!q.empty()) {
int size = q.size();
while (size--) { // so that we can count the steps
auto [i, j] = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int ni = i + directions[k];
int nj = j + directions[k+1];
if (ni >=0 && ni < m && nj >= 0 && nj < n && visited[ni][nj] == 1) {
visited[ni][nj] = 2;
countFreshOrange--;
q.push({ni, nj});
}
}
}
minutes++;
}
if (countFreshOrange == 0)
return minutes;
return -1;
}
};TODO
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
// to remove redundant and speed up the algo
unordered_set<string> wordSet(wordList.begin(), wordList.end());
if (wordSet.find(endWord) == wordSet.end()) {
return 0;
}
int length = 1;
queue<string> q;
q.push(beginWord);
wordSet.erase(beginWord);
while(!q.empty()) {
int size = q.size();
// loop through each BFS level
for (int s = 0; s < size; s++) {
string w = q.front();
q.pop();
if (w == endWord) {
return length;
}
for (int i = 0; i < w.length(); i++) {
char original = w[i];
for (char ch = 'a'; ch <= 'z'; ch++) {
w[i] = ch;
if (wordSet.find(w) != wordSet.end()) {
wordSet.erase(w);
q.push(w);
}
w[i] = original;
}
}
}
length++;
}
return 0;
}
};TODO
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if (n == 1) {
return {0};
}
vector<int> indegree(n, 0);
unordered_map<int, list<int>> g;
for (int i = 0; i < n; i++) {
g[i] = list<int>();
}
for (auto& edge : edges) {
int u = edge[0], v = edge[1];
indegree[u]++;
indegree[v]++;
g[u].push_back(v);
g[v].push_back(u);
}
queue<int> q;
for (int i = 0; i < n; i++) {
if (indegree[i] == 1) {
q.push(i);
}
}
int remaining = n;
while (remaining > 2) {
int s = q.size();
remaining -= s;
for (int i = 0; i < s; i++) {
int n = q.front();
q.pop();
cout << g.size() << endl;
for (int adj : g[n]) {
if (--indegree[adj] == 1) {
q.push(adj);
}
}
}
}
vector<int> result;
while(!q.empty()) {
result.push_back(q.front());
q.pop();
}
return result;
}
};class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
int results[n];
std::fill(results, results + n, INT_MAX);
results[src] = 0;
for (int i = 0; i <= k; i++) {
int resultsCopy[n];
copy(results, results + n, resultsCopy);
for (const auto& flight : flights) {
int s = flight[0];
int d = flight[1];
int w = flight[2];
if (results[s] == INT_MAX) {
continue;
}
// note here we compare with the resultsCopy because it
// could possibly be updated during the inner loop
if (results[s] + w < resultsCopy[d]) {
resultsCopy[d] = results[s] + w;
}
}
copy(resultsCopy, resultsCopy + n, results);
}
if (results[dst] == INT_MAX) {
return -1;
}
return results[dst];
}
};class Solution {
private:
class Vertex {
public:
Vertex(int t, int n): time(t), node(n) {}
bool operator<(const Vertex& other) const {
return time > other.time;
}
private:
int time;
int node;
friend class Solution;
};
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
unordered_map<int, vector<pair<int, int>>> v2e;
for (const auto& time : times) {
int src = time[0];
int dst = time[1];
int t = time[2];
if (v2e.find(src) != v2e.end()) {
v2e[src].push_back({dst, t});
} else {
v2e[src] = vector<pair<int, int>>();
v2e[src].push_back({dst, t});
}
}
int rst = 0;
std::set<int> visited;
std::priority_queue<Vertex> vq;
vq.push(Vertex(0, k));
while (!vq.empty()) {
Vertex v = vq.top();
vq.pop();
if (visited.find(v.node) != visited.end()) {
continue;
}
visited.insert(v.node);
rst = max(rst, v.time);
vector<pair<int, int>> edges = v2e[v.node];
for (const auto& e : edges) {
if (visited.find(e.first) == visited.end()) {
vq.push(Vertex(e.second + v.time, e.first));
}
}
}
if (visited.size() == n) {
return rst;
}
return -1;
}
};