# Graph topic
# 200. Number of Islands
## Question: (Medium)
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
## Solution: C++
```c=
class Solution {
public:
void DFS(vector<vector<char>>& grid, int** record, int i, int j, int r, int c){
if(i>=r || j>=c || i<0 || j<0)
return;
if(grid[i][j]=='0' || record[i][j]==1)
return;
record[i][j]=1;
DFS(grid, record, i, j+1, r, c); // right
DFS(grid, record, i+1, j, r, c); // bottom
DFS(grid, record, i, j-1, r, c); //left
DFS(grid, record, i-1, j, r, c); // up
}
int numIslands(vector<vector<char>>& grid) {
int**record = new int*[grid.size()];
int r = grid.size();
int c = grid[0].size();
int count = 0;
for(int i=0; i<grid.size(); i++)
record[i] = new int[grid[0].size()]{};
for(int i=0; i<grid.size(); i++){
for(int j=0; j<grid[0].size(); j++){
if(record[i][j]==0 && grid[i][j]=='1'){
DFS(grid, record, i, j, r, c);
count++;
}
}
}
return count;
}
};
```
## Notes
1. 用dfs跑在2d-matrix
2. 每跑完一次dfs，count+=1 (需要紀錄visit過的vertex)
3. 持續iterative這個grid，如果沒有visit過，則重複step2。
4. 需要注意一些邊界數值
---
# 695. Max Area of Island
## Question
You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
The area of an island is the number of cells with a value 1 in the island.
Return the maximum area of an island in grid. If there is no island, return 0.
Example 1:
Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.
Example 2:
Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0
## Solution(C++)
```c=
class Solution {
public:
int dfs(vector<vector<int>>& grid, int** visit, int i, int j){
if(i<0 || i>=grid.size() || j<0 || j>=grid[0].size())
return 0;
if(visit[i][j]==1 || grid[i][j]==0)
return 0;
visit[i][j] = 1;
// top bottom left right
return 1 + dfs(grid, visit, i-1, j)
+ dfs(grid, visit, i+1, j)
+ dfs(grid, visit, i, j-1)
+ dfs(grid, visit, i, j+1);
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int** visit = new int*[grid.size()];
int maxima = 0;
int val = 0;
for(int i=0; i<grid.size(); i++)
visit[i] = new int[grid[0].size()]{};
for(int i=0; i<grid.size(); i++){
for(int j=0; j<grid[i].size(); j++){
if(grid[i][j]==1 && visit[i][j]==0){
// using dfs to calculate the size of island
maxima = max(dfs(grid, visit, i, j), maxima);
}
}
}
return maxima;
}
};
```
## Notes:
* 2-d Depth-frist search to solve this question.
* 2-d的DFS通常就是**上下左右**的recursion。
* using a 2-d matrix to record whether this i-j is visited.
---
# 130. Surrounded Regions
## Question (Medium)
Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
## Solution (C++)
```python=
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
visit = [[0] * len(board[0]) for i in range(len(board))]
def dfs(i: int, j: int):
if i>=0 and i<len(board) and j>=0 and j<len(board[0]) and board[i][j]=="O" and visit[i][j]==0:
visit[i][j] = 1
board[i][j] = 'N'
dfs(i-1, j)
dfs(i+1, j)
dfs(i, j-1)
dfs(i, j+1)
for i in range(len(board)):
for j in range(len(board[0])):
# boarder
if i==0 or i==len(board)-1 or j==0 or j == len(board[0])-1:
dfs(i, j)
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == "O":
board[i][j] = "X"
elif board[i][j] == "N":
board[i][j] = "O"
```
## Notes
* 我們從2d-array的邊界開始做bfs，走過的座標label成"N"
* 最後再遍歷這個2d-array，若board[i][j]=="N"則改變成"O"
* 若board[i][j]=="O"，則表示這些座標跟**邊界無關**，所以改成"X"
---
# 207. Course Schedule
## Question (Medium)
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Constraints:
1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
All the pairs prerequisites[i] are unique.
## Solution (C++)
```c=
class Solution {
public:
typedef vector<vector<int>> graph;
bool dfs(graph& q, int val, int* visit){
bool ans = true;
if(visit[val]==2)
return true;
if(visit[val]==1)
return false;
visit[val]=1;
if(q[val].size()==0){
visit[val] = 2;
return true;
}
for(int i=0; i<q[val].size(); i++){
ans = ans && dfs(q, q[val][i], visit);
}
visit[val]=2;
return ans;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
graph g(numCourses);
int* visit = new int[numCourses]{};
for(int i=0; i<prerequisites.size(); i++)
g[prerequisites[i][1]].push_back(prerequisites[i][0]);
for(int i=0; i<numCourses; i++){
if(!dfs(g, i, visit))
return false;
}
return true;
}
};
```
## Notes
* 先建立adjacent matrix，做一個undirectd graph
* 透過DFS對這個graph做traversal
* 途中遇到重複的元素，即return false，這題很類似判斷graph有無cycle
* 以前會有刻板印象visit array只有0 or 1，但這題多一個2會很好判斷
* 0: 未訪問, 1: 正在訪問, 2: 已經訪問
---
# 310. Minimum Height Trees
## Question (Medium)
A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.
Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).
Return a list of all MHTs' root labels. You can return the answer in any order.
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.
## Solution (C++)
```c=
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
vector<vector<int>> adjacent_matrix(n);
vector<int> leaf_nodes;
vector<int> prev;
if(n==1)
return {0};
int* count = new int[n+10]{};
for(int i=0; i<edges.size(); i++){
adjacent_matrix[edges[i][0]].push_back(edges[i][1]);
adjacent_matrix[edges[i][1]].push_back(edges[i][0]);
count[edges[i][1]]++;
count[edges[i][0]]++;
}
for(int i=0; i<n; i++){
if(count[i]==1)
leaf_nodes.push_back(i);
else if(count[i]>1)
prev.push_back(i);
}
if(prev.size()==0)
prev = leaf_nodes;
while(true){
for(int i=0; i<leaf_nodes.size(); i++){
for(int j=0; j<adjacent_matrix[leaf_nodes[i]].size(); j++){
if(count[adjacent_matrix[leaf_nodes[i]][j]]!=1)
count[adjacent_matrix[leaf_nodes[i]][j]]--;
}
count[leaf_nodes[i]] = 0;
}
leaf_nodes.clear();
for(int i=0; i<n; i++){
if(count[i]==1)
leaf_nodes.push_back(i);
}
if(leaf_nodes.size()==0)
break;
prev = leaf_nodes;
}
return prev;
}
};
```
## Notes
>>完全沒想到可以這樣解QQ
1. 先找出leaf node，因為用leaf node當作root一定不會是minimun height。
2. 可以參考eample.1的第二張圖，[0,2,3]為leaf node，這三個點不管是誰作為root，一定都會經過node 1，代表不會比node 1作為節點還優。
3. 因此這題的作法就是找leaf node，leaf node以外的node即為適合作為root的選項(重複step.3，直到找不出leaf node為止，這時variable prev就是root的選項了)
---
# 841. Keys and Rooms
## Question (Medium)
There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.
When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.
Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.
Example 1:
Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation:
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.
Example 2:
Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.
## Solution (C++)
```c=
class Solution {
public:
void traversal(vector<vector<int>>& rooms, int* visit, int room_index){
if(visit[room_index]==1)
return;
visit[room_index] = 1;
int next_room = 0;
for(int i=0; i<rooms[room_index].size(); i++){
next_room = rooms[room_index][i];
traversal(rooms, visit, next_room);
}
}
bool canVisitAllRooms(vector<vector<int>>& rooms) {
int* visit = new int[rooms.size()]{};
bool ans = true;
traversal(rooms, visit, 0);
for(int i=0; i<rooms.size(); i++){
ans = ans && bool(visit[i]);
}
return ans;
}
};
```
## Notes:
* DFS
* 建立一個array visit，來記錄所有拜訪過的房間。
* 已拜訪過的，就不用繼續recursive。
---
# 547. Number of Provinces
## Question (Medium)
There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.
A province is a group of directly or indirectly connected cities and no other cities outside of the group.
You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.
Return the total number of provinces.
## Solution (C++)
```c=
class Solution {
public:
void dfs(vector<vector<int>>& isConnected, int* visit, int index){
if(visit[index]==1)
return;
visit[index]=1;
for(int i=0; i<isConnected[index].size(); i++){
if(isConnected[index][i] == 1){
dfs(isConnected, visit, i);
}
}
}
int findCircleNum(vector<vector<int>>& isConnected) {
// i = 0~n-1，做n次dfs
int* visit = new int[isConnected.size()]{};
int ans = 0;
for(int i=0; i<isConnected.size(); i++){
if(visit[i]==0){
dfs(isConnected, visit, i);
ans++;
}
}
return ans;
}
};
```
## Notes:
* 每做一次DFS，**都會找到一組province**。
* 有n個city，for迴圈判斷該city是否要執行dfs、是否已拜訪過。
---
# 994. Rotting Oranges
## Question (Medium)
You are given an m x n grid where each cell can have one of three values:
0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
## Solution (C++)
```c=
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int total_orange = 0;
int minutes = 0;
int direction[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int** visit = new int*[grid.size()];
vector<pair<int, int>> q;
for(int i=0; i<grid.size(); i++)
visit[i] = new int[grid[i].size()]{};
for(int i=0; i<grid.size(); i++){
for(int j=0; j<grid[0].size(); j++){
if(grid[i][j] == 1 || grid[i][j] == 2)
total_orange++;
if(grid[i][j] == 2){
q.push_back(make_pair(i, j));
}
}
}
// start bfs
int count = 0;
while(true){
vector<pair<int, int>> temp_q;
for(auto& rotten: q){
visit[rotten.first][rotten.second] = 1;
count++;
for(int i=0; i<4; i++){
int new_i = rotten.first + direction[i][0];
int new_j = rotten.second + direction[i][1];
if(new_i>=0&&new_i<grid.size()&& new_j>=0&&new_j<grid[0].size()){
if(visit[new_i][new_j] == 0 && grid[new_i][new_j] == 1){
temp_q.push_back(make_pair(new_i, new_j));
visit[new_i][new_j] = 1;
}
}
}
}
if(temp_q.size() == 0)
break;
minutes++;
q = temp_q;
}
return (count!=total_orange)?-1:minutes;
}
};
```
## Notes
---
# 437. Path Sum III
## Question (Medium)
Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.
The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).
## Solution (C++)
```c=
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int ans = 0;
void dfs(TreeNode* root, long long int targetSum){
if(root==NULL)
return;
if(root->val == targetSum){
ans++;
}
//因為選了root, targetSum就要更新為targetSum-root
dfs(root->left, targetSum-root->val);
dfs(root->right, targetSum-root->val);
}
int pathSum(TreeNode* root, int targetSum) {
if(root!=NULL){
//以root為首的path
dfs(root, targetSum);
//以root->left為首的path
int a = pathSum(root->left, targetSum);
int b = pathSum(root->right, targetSum);
}
return ans;
}
};
```
## Notes:
* 這題的recursive function用法很讚。
* 對所有的treeNode都執行一次dfs來計算有沒有等於TargetSum
---
## 934. Shortest Bridge
```c++=
class Solution {
public:
void dfs(int i, int j, vector<vector<int>>& g, vector<vector<int>>& visit, vector<pair<int, int>>& temp){
if(i>=0 && i<g.size() && j>=0 && j<g[0].size() && visit[i][j]==0){
visit[i][j] = 1;
if(g[i][j]==1)
temp.push_back(make_pair(i, j));
}
else
return;
if(g[i][j] == 1){
dfs(i-1, j, g, visit, temp);
dfs(i+1, j, g, visit, temp);
dfs(i, j-1, g, visit, temp);
dfs(i, j+1, g, visit, temp);
}
}
int shortestBridge(vector<vector<int>>& grid) {
vector<vector<int>> visit(grid.size(), vector<int>(grid[0].size()));
vector<vector<int>> visit2(grid.size(), vector<int>(grid[0].size()));
vector<pair<int, int>> record;
queue<pair<int, int>> q;
int find_one = 0;
for(int i=0; i<grid.size(); i++){
for(int j=0; j<grid[i].size(); j++){
if(grid[i][j] == 1){
dfs(i, j, grid, visit, record);
find_one = 1;
break;
}
}
if(find_one==1)
break;
}
for(int i=0; i<record.size(); i++){
visit2[record[i].first][record[i].second] = 1;
q.push(record[i]);
}
//cout<<"first island's size = "<<q.size()<<endl;
//對第一個island做bfs
int count = 0;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
while(q.size()!=0){
int qs = q.size();
for(int i=0; i<qs; i++){
pair<int, int> temp = q.front();
q.pop();
for(int j=0; j<4; j++){
int new_r = temp.first + dx[j];
int new_c = temp.second + dy[j];
if(new_r>=0&&new_r<grid.size()&&new_c>=0&&new_c<grid[0].size()){
if(visit2[new_r][new_c] == 0){
q.push(make_pair(new_r, new_c));
visit2[new_r][new_c] = 1;
if(grid[new_r][new_c] == 1)//代表碰到地2個island
return count;
}
}
}
}
count++;
}
return 0;
}
};
```
### Notes:
1. 因為題目講明了，只會有2座island
2. 先用dfs找出任一一座island，並基於這座island做bfs，若碰到grid[i][j] = 1，就表示碰到另外一座island了
---
## 863. All Nodes Distance K in Binary Tree
```python=
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from queue import Queue
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
# transfer this Tree to Graph
adj = {}
def dfs(node: TreeNode):
if node.val not in adj.keys():
adj[node.val] = []
if node.left != None:
if node.left.val not in adj.keys():
adj[node.left.val] = []
adj[node.val].append(node.left.val)
adj[node.left.val].append(node.val)
dfs(node.left)
if node.right != None:
if node.right.val not in adj.keys():
adj[node.right.val] = []
adj[node.val].append(node.right.val)
adj[node.right.val].append(node.val)
dfs(node.right)
dfs(root)
# start bfs
ans = []
q = Queue()
q.put((target.val, 0))
visit = {}
for key in adj.keys():
visit[key] = 0
visit[target.val] = 1
while not q.empty():
qs = q.qsize()
for i in range(qs):
node = q.get()
if node[1] == k:
ans.append(node[0])
for j in range(len(adj[node[0]])):
if visit[adj[node[0]][j]] == 0:
q.put((adj[node[0]][j], node[1]+1))
visit[adj[node[0]][j]] = 1
return ans
```
### Notes:
1. 可以發現這題把tree轉成graph會比較好做
2. 先跑一次dfs，並同時建立adj matrix
3. 從target node開始，對整個graph做bfs
Sign in with Wallet
Connect another wallet