Algorithms & Data Structures : Graph : Problems

Problems

LeetCode : 785. Is Graph Bipartite?
[BFS]

LeetCode : 207. Course Schedule
[topological sort]

LeetCode : 210. Course Schedule II
[topological sort]

LeetCode : 269. Alien Dictionary
[topological sort]

LeetCode : 778. Swim in Rising Water
[BFS][priority queue]

LeetCode : 1820. Maximum Number of Accepted Invitations
[DFS][Maximum Bipartite Matching]

LeetCode : 2115. Find All Possible Recipes from Given Supplies
[DFS]

LeetCode 1059. All Paths from Source Lead to Destination
[Cycle Detection][DFS]

LeetCode : 2285. Maximum Total Importance of Roads
[sorting][graph]

LeetCode : 1034. Coloring A Border
[DFS]

LeetCode : 802. Find Eventual Safe States
[graph][DFS]

LeetCode : 1192. Critical Connections in a Network
[Articulation Bridge]

LeetCode : 329. Longest Increasing Path in a Matrix
[topological sort]

LeetCode : 924. Minimize Malware Spread

LeetCode : 928. Minimize Malware Spread II

LeetCode : 1568. Minimum Number of Days to Disconnect Island

LeetCode : 785. Is Graph Bipartite?

BFS 遍尋圖。
複雜度: O( V * E ) // 其實沒有很確定 QQ

class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
vector<int> type = vector<int>(graph.size(), 0);

queue<int> q;

for(int i = 0;i < graph.size();i++) {
if(type[i] == 0) {
// 只要是沒看過的節點,一律設為 type 1
q.push(i);
type[i] = 1;
} else {
continue;
}
// BFS
while(!q.empty()) {
int nown = q.front();
q.pop();
// 所有的邊都遍尋一遍,看有沒有不合規則的
for(int j = 0;j < graph[nown].size();j++) {
if(type[graph[nown][j]] == type[nown]) {
// 跟節點同一 type ==> 不符規則
return false;
} else if(type[graph[nown][j]] == 0) {
// 假如是還沒選定 type 的節點
// 填上與 nown 節點不同的 type
q.push(graph[nown][j]);
if(type[nown] == 1) {
type[graph[nown][j]] = 2;
} else {
type[graph[nown][j]] = 1;
}
} else {
// 已經選定 type,且符合規則
// 不須遍尋,直接跳過
}
}
}
}
return true;
}
};

LeetCode : 207. Course Schedule

使用 topological sort 來偵測環

TODO :嘗試其他偵測環的方式

class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {

vector<int> inDegree = vector<int>(numCourses, 0);
unordered_map<int, vector<int>> g;

for(int i = 0;i < prerequisites.size();i++) {
inDegree[prerequisites[i][0]]++;
g[prerequisites[i][1]].push_back(prerequisites[i][0]);
}

queue<int> q;
int numOfToPoSort = 0;

for(int i = 0;i < inDegree.size();i++) {
if(0 == inDegree[i]) {
q.push(i);
}
}

while(!q.empty()) {
int nown = q.front();
numOfToPoSort++;
q.pop();

vector<int> &v = g[nown];
for(int i = 0;i < v.size();i++) {
inDegree[v[i]]--;
if(0 == inDegree[v[i]]) {
q.push(v[i]);
}
}
}
return numCourses == numOfToPoSort;
}
};

LeetCode : 210. Course Schedule II

正宗 topological sort 題目

class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> inDegree = vector<int>(numCourses, 0);
unordered_map<int, vector<int>> g;
for(int i = 0;i < prerequisites.size();i++) {
inDegree[prerequisites[i][0]]++;
g[prerequisites[i][1]].push_back(prerequisites[i][0]);
}

queue<int> q;

for(int i = 0;i < numCourses;i++) {
if(0 == inDegree[i]) {
q.push(i);
}
}

vector<int> toPoSort;

while(!q.empty()) {
int nown = q.front();
toPoSort.push_back(nown);
q.pop();

vector<int> &v = g[nown];
for(int i = 0;i < v.size();i++) {
inDegree[v[i]]--;
if(0 == inDegree[v[i]]) {
q.push(v[i]);
}
}
}

return toPoSort.size() == numCourses ? toPoSort : vector<int>(0);
}
};

LeetCode : 269. Alien Dictionary

TODO:看一下其他人是怎麼做的

/*
[a,b,c]
[a,b]
--> 這類排序錯誤直接可斷定為 ""
*/
class Solution {
public:
string alienOrder(vector<string>& words) {
string s;

int numWord = 0;
unordered_map<char, vector<char>> g;
unordered_map<char, unordered_map<char, bool>> visited;
vector<int> inDegree = vector<int>(26, 0);
vector<bool> exist = vector<bool>(26, false);

for(int i = 0;i < words.size();i++) {
for(int j = 0;j < words[i].size();j++) {
if(!exist[words[i][j] - 'a']) {
exist[words[i][j] - 'a'] = true;
numWord++;
}
}
for(int j = i + 1;j < words.size();j++) {
int len = min(words[i].size(), words[j].size());
int index;

// check the input is correct
// ( lexicographically )
for(index = 0;index < len;index++) {
if(words[i][index] != words[j][index]) {
break;
}
}
// the input is not correct!
if(index == words[j].size() && index != words[i].size()) {
return "";
}


for(int q = 0;q < len;q++) {
if(words[i][q] != words[j][q]) {
// 使用 visited 來避免加入相同的邊
if(!visited[words[i][q]][words[j][q]]) {
visited[words[i][q]][words[j][q]] = true;
inDegree[words[j][q] - 'a']++;
g[words[i][q]].push_back(words[j][q]);
}
break;
}
}
}
}

queue<char> q;
for(char i = 0;i < 26;i++) {
if(0 == inDegree[i] && exist[i]) {
q.push(i + 'a');
}
}

// topological sort
while(!q.empty()) {
char nowc = q.front();
s += nowc;
q.pop();

vector<char> &v = g[nowc];

for(int i = 0;i < v.size();i++) {
inDegree[v[i] - 'a']--;
if(0 == inDegree[v[i] - 'a']) {
q.push(v[i]);
}
}
}
return s.size() == numWord ? s : "";
}
};

LeetCode : 778. Swim in Rising Water

使用 priority queue 去記錄海拔最小的節點,並從海拔較小的節點開始進行 BFS。

class Solution {
private:
int t = 0;
int X[4] = {0, 0, 1, -1};
int Y[4] = {1, -1, 0, 0};
public:
int swimInWater(vector<vector<int>>& grid) {
vector<vector<bool>> visited = vector<vector<bool>>(grid.size(), vector<bool>(grid[0].size(), false));
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;

pq.push({grid[0][0], 0, 0});
visited[0][0] = true;

while(!pq.empty()) {
vector<int> nown = pq.top();
pq.pop();

int e = nown[0];
int x = nown[1];
int y = nown[2];

if(x == grid.size() - 1 &&
y == grid[0].size() - 1) {
return max(e, t);
}

if(e > t) {
t = e;
}

for(int i = 0;i < 4;i++) {
int newx = x + X[i];
int newy = y + Y[i];

if(newx >= 0 && newx < grid.size() &&
newy >= 0 && newy < grid[0].size() && !visited[newx][newy]) {
visited[newx][newy] = true;
pq.push({grid[newx][newy], newx, newy});
}
}
}

return 0;
}
};

LeetCode : 1820. Maximum Number of Accepted Invitations

稀有的 bipartite matching 題目。
TODO : 用 Flow 的概念作這一題。

// maximum bipartite matching
// Reference
// https://web.ntnu.edu.tw/~algo/Matching.html#4
/*
Cardinality ( 基數 )
一個匹配擁有的匹配邊數目
Alternating Path ( 交錯路徑 )
Alternating Cycle ( 交錯環 )
在一張存在匹配的圖上,匹配邊和未匹配邊彼此相間的一條路徑與一個環
Augmenting Path ( 擴充路徑 )
一條交錯路徑,第一個點和最後一個點都是未匹配點。因此第一條邊和最後一條邊都是未匹配邊
擴充路徑有個更有趣的特性:顛倒擴充路徑上的匹配邊和未匹配邊,可以改變匹配,並且讓 Cardinality 加一
https://web.ntnu.edu.tw/~algo/Matching.html#4*/class Solution {
private:
vector<int> bm; // boys match
vector<int> gm; // girls match

vector<vector<int>> bg; // boys graph
vector<vector<int>> gg; // girls graph

bool dfs(int b, vector<vector<int>> &grid, vector<bool> &visited) {

for(int i = 0;i < bg[b].size();i++) {
int girl = bg[b][i];
if(!visited[girl]) {
visited[girl] = true;
if(-1 == gm[girl] || dfs(gm[girl], grid, visited)) {
bm[b] = girl;
gm[girl] = b;
return true;
}
}
}

return false;
}

public:
int maximumInvitations(vector<vector<int>>& grid) {
vector<bool> visited;

bm = vector<int>(grid.size(), -1);
gm = vector<int>(grid[0].size(), -1);

bg = vector<vector<int>>(grid.size());
gg = vector<vector<int>>(grid[0].size());

for(int i = 0;i < grid.size();i++) {
for(int j = 0;j < grid[0].size();j++) {
if(1 == grid[i][j]) {
bg[i].push_back(j);
gg[j].push_back(i);
}
}
}

int num = 0;
for(int i = 0;i < bg.size();i++) {
visited = vector<bool>(gg.size(), false);
if(dfs(i, grid, visited)) {
// 每找到一個 Augmenting Path , Cardinality 加 1
num++;
}
}

return num;
}
};

LeetCode : 2115. Find All Possible Recipes from Given Supplies

注意有可能會出現環。

TODO : 效能太差。

class Solution {
private:

bool dfs(string &s, vector<vector<string>>& ingredients, unordered_map<string, bool> &s2b, unordered_map<string, int> &s2i, unordered_map<string, bool> &s2v) {
if(s2b.find(s) != s2b.end()) {
return true;
}

if(s2i.find(s) == s2i.end()) {
return false;
}

if(s2v[s]) {
return false;
}
s2v[s] = true;

int index = s2i[s];


for(int i = 0;i < ingredients[index].size();i++) {
if(s2b.find(ingredients[index][i]) == s2b.end()) {
if(!dfs(ingredients[index][i], ingredients, s2b, s2i, s2v)) {
return false;
}
}
}

s2v[s] = false;
return true;
}

public:

vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
vector<string> ans;
unordered_map<string, bool> s2b;
unordered_map<string, int> s2i;
unordered_map<string, bool> s2v;

for(int i = 0;i < supplies.size();i++) {
s2b[supplies[i]] = true;
}

for(int i = 0;i < recipes.size();i++) {
s2i[recipes[i]] = i;
}

for(int i = 0;i < recipes.size();i++) {
if(dfs(recipes[i], ingredients, s2b, s2i, s2v)) {
ans.push_back(recipes[i]);
}
}

return ans;
}
};

LeetCode 1059. All Paths from Source Lead to Destination

TODO : 太慢,想些辦法加速

class Solution {
public:

bool dfs(int index, unordered_map<int, vector<int>> &g, unordered_map<int, int> &state) {

vector<int> &edges = g[index];
for(int i = 0;i < edges.size();i++) {
if(0 == state[edges[i]]) {
state[edges[i]] = 1;
bool res = dfs(edges[i], g, state);
if(!res) {
return false;
}
state[edges[i]] = 2;
} else if(1 == state[edges[i]]) {
return false;
} else if(2 == state[edges[i]]) {

}
}

return true;
}

bool dfs2(int index, unordered_map<int, vector<int>> &g, unordered_map<int, int> &state, int dest) {
if(index == dest) {
return true;
}

// 最後的點不是 dest
if(0 == g[index].size()) {
return false;
}

vector<int> &edges = g[index];
for(int i = 0;i < edges.size();i++) {
if(0 == state[edges[i]]) {
state[edges[i]] = 1;
bool res = dfs2(edges[i], g, state, dest);
if(!res) {
return false;
}
state[edges[i]] = 2;
} else if(1 == state[edges[i]]) {
return false;
} else if(2 == state[edges[i]]) {

}
}

return true;
}


bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {

unordered_map<int, vector<int>> g;
for(int i = 0;i < edges.size();i++) {
g[edges[i][0]].push_back(edges[i][1]);
}

// destination 不能有 outgoing edge
if(0 != g[destination].size()) {
return false;
}

// 不能有環
// --> 不該檢查所有的環,只需檢查從 source 開始有無環
// 0 : not visit
// 1 : visiting
// 2 : visited
unordered_map<int, int> state;
/*for(int i = 0;i < n;i++) {
bool res = dfs(i, g, state);
if(!res) {
return false;
}
}*/

// 從 source 到 dest
state.clear();
return dfs2(source, g, state, destination);
}
};

LeetCode : 2285. Maximum Total Importance of Roads

out degree 越多的節點,就該有越高的權重

#define LL long long
class Solution {
public:
long long maximumImportance(int n, vector<vector<int>>& roads) {

vector<int> outd = vector<int>(n, 0);
for(int i = 0;i < roads.size();i++) {
outd[roads[i][0]]++;
outd[roads[i][1]]++;
}

LL ans = 0;
sort(outd.begin(), outd.end());

LL nowv = n;
for(int i = outd.size() - 1;i >= 0;i--) {
ans += nowv * outd[i];
nowv--;
}

return ans;
}
};

LeetCode : 1034. Coloring A Border

class Solution {
public:

int X[4] = {1, -1, 0, 0};
int Y[4] = {0, 0, 1, -1};

void dfs(int x, int y, vector<vector<int>> &ans, vector<vector<bool>> &visited, vector<vector<int>>& grid, int ori, int color) {

bool f = false;
for(int i = 0;i < 4;i++) {
int newx = x + X[i];
int newy = y + Y[i];



if(newx >= 0 && newx < grid.size() &&
newy >= 0 && newy < grid[0].size()) {

if(grid[newx][newy] != ori) {
f = true;
}

if(!visited[newx][newy]) {
visited[newx][newy] = true;

if(grid[newx][newy] == ori) {
dfs(newx, newy, ans, visited, grid, ori, color);
}
}
} else {
f = true;
}
}

if(f) {
ans[x][y] = color;
}
}

vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
vector<vector<int>> ans = grid;
vector<vector<bool>> visited = vector<vector<bool>> (grid.size(), vector<bool>(grid[0].size(), false));
if(ans[row][col] == color) {
return ans;
}

visited[row][col] = true;
dfs(row, col, ans, visited, grid, grid[row][col], color);

return ans;
}
};

LeetCode : 802. Find Eventual Safe States

class Solution {
public:

void dfs(int nown, vector<vector<int>>& g, vector<int> &s, vector<int> &t) {

vector<int> &e = g[nown];

for(int i = 0;i < e.size();i++) {
if(1 == s[e[i]]) {
t[nown] = 1;
} else if(2 == s[e[i]]) {

// 碰到 un-safe 的點,
// 自己也會變成 un-safe
if(1 == t[e[i]]) {
t[nown] = 1;
}

} else if(0 == s[e[i]]) {
// 標示為 visiting
s[e[i]] = 1;
dfs(e[i], g, s, t);

// 碰到 un-safe 的點,
// 自己也會變成 un-safe
if(1 == t[e[i]]) {
t[nown] = 1;
}

}
}

// 假如都沒撞到
if(0 == t[nown]) {
t[nown] = 2;
}

// 標示為 visited
s[nown] = 2;
}

vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
vector<int> ans;
// unordered_map<int, int>

// status : 0 : not visited
// status : 1 : visiting
// status : 2 : visited
vector<int> status = vector<int>(graph.size(), 0);

// type : 0 : unknown
// type : 1 : not safe
// type : 2 : safe
vector<int> type = vector<int>(graph.size(), 0);

for(int i = 0;i < graph.size();i++) {
if(0 == status[i]) {
dfs(i, graph, status, type);
}
}

for(int i = 0;i < type.size();i++) {
if(2 == type[i]) {
ans.push_back(i);
}
}

sort(ans.begin(), ans.end());

return ans;
}
};

Reference

topological sort — 演算法筆記

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store