# Graph

###### tags: `LeetCode筆記`

## :memo: 一、Disjoint Set
Each graph consists of vertices and edges. The root vertices are in blue.

* The **find** function finds the root node of a given vertex.
* For example, the output of the find function for vertex 3 is 0.
* The **union** function unions two vertices and makes their root nodes the same.
* If we union vertex 4 and vertex 5, their root node will become the same, which means the union function will modify the root node of vertex 4 or vertex 5 to the same root node.

兩種方式實現Find和Union:

* Implementation with **Quick Find**: in this case, **the time complexity of the find function will be O(1)**. However, **the union function will take more time with the time complexity of O(N)**.
* Implementation with **Quick Union**: compared with the Quick Find implementation, **the time complexity of the union function is better**. Meanwhile, **the find function will take more time in this case**.

### 1. Quick Find
**find**
是直接用root[node]去存該node的根所以都會存node最新的根
->O(1)
**unionSet**
是把所有node都掃過一次並更新成最新的根
->O(N)

class UnionFind {
public:
    UnionFind(int sz) : root(sz) {
        for (int i = 0; i < sz; i++) {
            root[i] = i;
        }
    }

    int find(int x) {
        return root[x];
    }

    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            for (int i = 0; i < root.size(); i++) {
                if (root[i] == rootY) {
                    root[i] = rootX;
                }
            }
        }
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }

private:
    vector<int> root;
};

**Time Complexity:**
Union-find Constructor O(N)
Find O(1)
Union O(N)
Connected O(1)

### 2. Quick Union
**find**
是不斷的找父node直到找到根
->O(N)幾乎不會到N那麼大
**unionSet**
是先找出兩個node的根，再把其中一個nodeA的根A的父node記錄成另外一個nodeB的根B
->O(N)幾乎不會到2N

class UnionFind {
public:
    UnionFind(int sz) : root(sz) {
        for (int i = 0; i < sz; i++) {
            root[i] = i;
        }
    }

    int find(int x) {
        while (x != root[x]) {
            x = root[x];
        }
        return x;
    }

    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            root[rootY] = rootX;
        }
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }

private:
    vector<int> root;
};

**Time Complexity:**
Union-find Constructor O(N)
Find O(N)
Union O(N)
Connected O(N)

**Note:**
1. **N** is the number of vertices in the graph.
1. In the worst-case scenario, the number of operations to get the root vertex will be **H** where **H** is the height of the tree.
1. Because this implementation does not always point the root of the shorter tree to the root of the taller tree, **H** can be at most **N** when the tree forms a linked list.

### 3. Union by Rank

class UnionFind {
public:
    UnionFind(int sz) : root(sz), rank(sz) {
        for (int i = 0; i < sz; i++) {
            root[i] = i;
            rank[i] = 1;
        }
    }

    int find(int x) {
        while (x != root[x]) {
            x = root[x];
        }
        return x;
    }

    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                root[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                root[rootX] = rootY;
            } else {
                root[rootY] = rootX;
                rank[rootX] += 1;
            }
        }
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }

private:
    vector<int> root;
    vector<int> rank;
};

**Time Complexity**
Union-find Constructor O(N)
Find O(logN)
Union O(logN)
Connected O(logN)

### 4. Path Compression Optimization
#### find function optimization

class UnionFind {
public:
    UnionFind(int sz) : root(sz) {
        for (int i = 0; i < sz; i++) {
            root[i] = i;
        }
    }

    int find(int x) {
        if (x == root[x]) {
            return x;
        }
        return root[x] = find(root[x]);
    }

    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            root[rootY] = rootX;
        }
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }

private:
    vector<int> root;
};

**Time Complexity**
Union-find Constructor O(N)
Find O(logN)
Union O(logN)
Connected O(logN)

### 5. Optimized “disjoint set” with Path Compression and Union by Rank

class UnionFind {
public:
    UnionFind(int sz) : root(sz), rank(sz) {
        for (int i = 0; i < sz; i++) {
            root[i] = i;
            rank[i] = 1;
        }
    }

    int find(int x) {
        if (x == root[x]) {
            return x;
        }
        return root[x] = find(root[x]);
    }

    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                root[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                root[rootX] = rootY;
            } else {
                root[rootY] = rootX;
                rank[rootX] += 1;
            }
        }
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }

private:
    vector<int> root;
    vector<int> rank;
};

**Time Complexity**
Union-find Constructor O(N)
Find O(α(N))
Union O(α(N))
Connected O(α(N))

**Note**:
1. N is the number of vertices in the graph. α refers to the Inverse Ackermann function.
1. In practice, we assume it's a constant. In other words, O(α(N)) is regarded as O(1) on average.

**Tips**:
* understand and memorize the implementation of “disjoint set with path compression and union by rank”.
* practice solving the exercise problems using the “disjoint set” data structure.

## :memo: Number of Provinces (Medium)


### 作法
先將每一個點的parent設為-1，接著使用union將每個點group起來並改變點的parent指向聯合在一起的點，最後數看看有幾個-1就有幾個group

int find(int* parent, int i) {
    if (parent[i] == -1)
    {
        return i;
    }
    
    return find(parent, parent[i]);
}

void _union(int* parent, int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    
    if (xset != yset)
    {
        parent[xset] = yset;
    }
}

int findCircleNum(int** isConnected, int isConnectedSize, int* isConnectedColSize) {
    int parent[201];
    
    for (int i = 0; i < 201; i++)
    {
        parent[i] = -1;
    }
    
    for (int i = 0; i < isConnectedSize; i++)
    {
        for (int j = 0; j < isConnectedSize; j++)
        {
            if (isConnected[i][j] == 1 && i != j)
            {
                _union(parent, i, j);
            }
        }
    }
    int count = 0;
    for (int i = 0; i < isConnectedSize; i++)
    {
        if (parent[i] == -1)
        {
            count++;
        }
    }
    
    return count;
}

## :memo: Number of Connected Components in an Undirected Graph (Medium)


### 作法
這題與Number of Provinces不一樣的地方在於本題是用hashtable去記錄有哪幾個點是group的root(hashtable[i]>0)

int find(int* root, int X) {
    return root[X];
}

void _union(int* root, int X, int Y, int n) {
    int rootX = find(root, X);
    int rootY = find(root, Y);
    
    if (rootX != rootY)
    {
        for (int i = 0; i < n; i++)
        {
            if (root[i] == rootY)
            {
                root[i] = rootX;
            }
        }    
    }    
}

int countComponents(int n, int** edges, int edgesSize, int* edgesColSize) {
    int root[2001];
    int hashtable[2001];
    int count = 0;
    
    for (int i = 0; i < n; i++)
    {
        root[i] = i;
        hashtable[i] = 0;
    }
    
    for (int i = 0; i < edgesSize; i++)
    {
        int A = edges[i][0];
        int B = edges[i][1];
        
        _union(root, A, B, n);
    }
    
    for (int i = 0; i < n; i++)
    {
        hashtable[root[i]]++;
    }
    
    for (int i = 0; i < n; i++)
    {
        if (hashtable[i] > 0)
        {
            count++;
        }
    }
    
    return count;
}

## :memo: Graph Valid Tree (Medium)


There are no self-loops or repeated edges.

### 作法
1.檢查是否為n-1條邊
2.檢查一條邊的兩個點Union時是否具有相同的root，若有則為false

int find(int* parent, int* A) {
    int root = *A;
    
    while (parent[root] != root)
    {
        root = parent[root];
    }
    while (*A != root)
    {
        int oldRoot = parent[*A];
        parent[*A] = root;
        *A = oldRoot;
    }

    return root;
}

int _union(int* parent, int* size, int A, int B) {
    int rootA = find(parent, &A);
    int rootB = find(parent, &B);
    
    if (rootA == rootB)
    {
        return false;
    }
    
    if (size[rootA] < size[rootB])
    {
        parent[rootA] = rootB;
        size[rootB] += size[rootA];
    }
    else
    {
        parent[rootB] = rootA;
        size[rootA] += size[rootB];
    }
    
    return true;
}

bool validTree(int n, int** edges, int edgesSize, int* edgesColSize) {
    int parent[5000];
    int size[5000];
    
    for (int node = 0; node <= edgesSize; node++)
    {
        parent[node] = node;
        size[node] = 1;
    }
    
    if (edgesSize != n - 1)
    {
        return false;
    }
    
    for (int i = 0; i < edgesSize; i++)
    {
        int A = edges[i][0];
        int B = edges[i][1];
        
        if (!_union(parent, size, A, B))
        {
            return false;
        }
    }
    
    return true;
}

## :memo: *The Earliest Moment When Everyone Become Friends (Medium)
Return the earliest time for which every person became acquainted with every other person.
If there is no such earliest time, return -1.

### 作法
這題要依照時間先進行排序，再去做Union

int cmp(void *a, void *b) {
    int *x = *(int**)a;
    int *y = *(int**)b;
    
    return (x[0] > y[0]);
}

int find(int* group, int A){
    if (group[A] != A)
    {
        group[A] = find(group, group[A]);
    }

    return group[A];
}

int _union(int* group, int* rank,int A, int B, int n) {
    int groupA = find(group, A);
    int groupB = find(group, B);
    bool isMerged = false;
    
    if (groupA == groupB)
    {
        return isMerged;
    }
        
    isMerged = true;
    
    if (rank[groupA] > rank[groupB])
    {
        group[groupB] = groupA;
    }
    else if (rank[groupA] < rank[groupB])
    {
        group[groupA] = groupB;
    }     
    else 
    {
        group[groupA] = groupB;
        rank[groupB] += 1;
    }
    
    return isMerged;
}

int earliestAcq(int** logs, int logsSize, int* logsColSize, int n) {
    int group[101];
    int rank[101];
    int groupCount = n;
    
    //Sort the logs based on the time
    qsort(logs, logsSize, sizeof(int*), cmp);
    
    for (int person = 0; person < n; person++)
    {
        group[person] = person;
        rank[person] = 0;
    }
    
    for (int i = 0; i < logsSize; i++)
    {
        int A = logs[i][1];
        int B = logs[i][2];
    
        if (_union(group, rank, A, B, n))
        {
            groupCount--;
        } 
        
        if (groupCount == 1) 
        {
            return logs[i][0];
        }
    }
    
    return -1;
}

## :memo: Evaluate Division (Medium)
**Input:** equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
**Output:** [6.00000,0.50000,-1.00000,1.00000,-1.00000]
**Explanation:**
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]

### 作法

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        //we will be using unordered_map to store the data
        unordered_map<string, unordered_map<string, double>> adj;
        
        //create a adj list 
        createAdjList(adj, equations, values);
        
        vector<double> res(queries.size());
        //calculate result of every query
        for (int i = 0; i < queries.size(); i++)
        {
            unordered_set<string> visited;
            res[i] = dfs(queries[i][0], queries[i][1], visited, adj);
        }
        return res;
        
    }
    
    double dfs(string start, string end, unordered_set<string>& visited, unordered_map<string, unordered_map<string, double>>& adj)
    {
        //we cant find the  given string
        if (adj.find(start) == adj.end())
            return -1.0;
        //if we have got our string end 
        if (adj[start].find(end) != adj[start].end())
            return adj[start][end];
        visited.insert(start);
        //explore all possible paths 
        //if any one of them doesnot returns -1.0 we got our solution 
        for (auto i : adj[start])
        {
            //we dont want to revisit our previously visited strings
            if (!visited.count(i.first))
            {
                double ans = dfs(i.first, end, visited, adj);
                if (ans != -1.0)
                    return (double) ans * (i.second);
            }       
        }
        return -1.0;
    }
    
    void createAdjList(unordered_map<string, unordered_map<string, double>>& adj, vector<vector<string>>& equations, vector<double>& values)
    {
        for (int i = 0; i < equations.size(); i++)
        {
            string from = equations[i][0];
            string to = equations[i][1];
            adj[from].insert({to, values[i]});
            adj[to].insert({from, (double) 1 / values[i]});
        }
            
    }
};

## :memo: Optimize Water Distribution in a Village (Hard)

**Input:** n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
**Output:** 3
**Explanation:** The image shows the costs of connecting houses using pipes.
The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.

### 作法
關鍵在要把**建立井當作一條邊**記錄成本，接著在記錄管線成本，在排序邊成本array，排序完後進行union並加總cost

int cmp(void *a, void *b) {
    int *x = *(int**)a;
    int *y = *(int**)b;
    
    return (x[2] > y[2]);
}

int find(int* group, int person) {
    if (group[person] != person)
    {
        group[person] = find(group, group[person]);
    }
    
    return group[person];
}

bool _union(int* group, int* rank, int person1, int person2) {
    int group1 = find(group, person1);
    int group2 = find(group, person2);
    if (group1 == group2)
    {
        return false;
    }
    
    if (rank[group1] > rank[group2])
    {
        group[group2] = group1;
    }
    else if (rank[group1] < rank[group2])
    {
        group[group1] = group2;
    }
    else
    {
        group[group1] = group2;
        rank[group2]++;
    }
    
    return true;
}

// key point: see installing a well as one edge with weight!
int minCostToSupplyWater(int n, int* wells, int wellsSize, int** pipes, int pipesSize, int* pipesColSize) {
    int** orderedEdges = (int**) malloc(sizeof(int*) * (n + 1 + pipesSize));
    for (int i = 0; i < n + 1 + pipesSize; i++)
    {
        orderedEdges[i] = (int*) malloc(sizeof(int) * 3);
        for (int j = 0; j < 3; j++)
        {
            orderedEdges[i][j] = 0;
        }
    }
    
    int group[10001];
    int rank[10001];
    int totalCost = 0;
    
    for (int i = 0; i < n + 1; i++)
    {
        group[i] = i;
        rank[i] = 0;
    }
    
    for (int i = 0; i < wellsSize; i++)
    {
        orderedEdges[i][0] = 0;
        orderedEdges[i][1] = i + 1;
        orderedEdges[i][2] = wells[i];
    }
    
    for (int i = wellsSize; i < wellsSize + pipesSize; i++)
    {
        orderedEdges[i][0] = pipes[i - wellsSize][0];
        orderedEdges[i][1] = pipes[i - wellsSize][1];
        orderedEdges[i][2] = pipes[i - wellsSize][2];
    }
    
    qsort(orderedEdges, wellsSize+pipesSize, sizeof(int*), cmp);
    
    for (int i = 0; i < wellsSize + pipesSize; i++)
    {
        int house1 = orderedEdges[i][0];
        int house2 = orderedEdges[i][1];
        int cost = orderedEdges[i][2];
        
        if (_union(group, rank, house1, house2))
        {
            totalCost += cost;
        }
    }
    
    return totalCost;
}

## :memo: emplace_back()和push_back()的區別
emplace_back() 和 push_back() 的差別，就在於底層實作的機制不同。
* push_back() 在容器尾部添加元素時，首先會創建這個元素，然後再將這個元素拷貝或移動到容器中（如果是拷貝的話，事後會自行銷毀先前創建的這個元素）
* emplace_back() 在實現 時，則是直接在容器尾部創建這個元素，省去了拷貝或移動元素的過程。

## :memo: 二、Depth-First Search Algorithm
Q: How can we find all of its vertices, and how can we find all paths between two vertices?
A: Depth-First Search Algorithm

1. Traverse **all vertices** in a “graph”
利用Stack去依照深度往下(pop)將追蹤中的點的neighbor填入stack，接著繼續追蹤(pop)並將沒被visited的點記錄為path，如此便追蹤所有的點
2. Traverse **all paths between any two vertices** in a “graph”
關鍵在於要將run過的路線記錄儲存在Stack中例如:A-B-C整條放入Stack，然後如搜尋整張圖一樣跑演算法，當找到終點時(新增一條路線)後要remark往回走已經走過的路線(將visited改為0，並run之前放在Stack的path)

### 1. Find if Path Exists in Graph
#### 作法 C

struct node {
    int val;
    int numneighbors;
    struct node** neighbors;
};

struct node** nodes_Create(int num_node) {
    struct node** nodes = (struct node**) malloc(sizeof(struct node*) * num_node);
    for (int i = 0; i < num_node; i++)
    {
        nodes[i] = (struct node*) malloc(sizeof(struct node));
        nodes[i]->val = i;
        nodes[i]->numneighbors = 0;
        nodes[i]->neighbors = (struct node**) malloc(sizeof(struct node*));
    }
    
    return nodes;
}

void nodes_Setting(struct node** nodes, int** edges, int edgesSize) {
    for (int i = 0; i < edgesSize; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            nodes[edges[i][j]]->neighbors = (struct node**) realloc(nodes[edges[i][j]]->neighbors, sizeof(struct node*) * ((nodes[edges[i][j]]->numneighbors) + 1));
            nodes[edges[i][j]]->neighbors[nodes[edges[i][j]]->numneighbors] = nodes[edges[i][!j]];
            nodes[edges[i][j]]->numneighbors += 1;
        }
    }
}

void dfs(struct node* s,struct node** visited, int destination, bool* result) {
    visited[s->val] = 1;
    // printf("-%d-",s->val);
    if (s->val == destination)
    {
        *result = true;
        
        return;
    }
    
    if (s->numneighbors == 0)
    {
        return;
    }
    
    for (int i = 0; i < s->numneighbors; i++)
    {
        if (visited[s->neighbors[i]->val] == 0)
        {
            dfs(s->neighbors[i], visited, destination, result);
        }
    }
}

bool validPath(int n, int** edges, int edgesSize, int* edgesColSize, int source, int destination) {
    struct node** nodes = nodes_Create(n);    
    nodes_Setting(nodes,edges,edgesSize);
    
    struct node* visited[200000] = {NULL};
    bool result = false;
    
//     for (int i = 0; i < n; i++)
//     {
//         printf("neighbors of node %d: ", i);
//         for (int j = 0; j < nodes[i]->numneighbors; j++)
//         {
//             printf("%d ",nodes[i]->neighbors[j]->val);
//         }
//         printf("\n");
//     }
    
    dfs(nodes[source], visited, destination, &result);
    
    return result;
}

#### 作法 C++

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int start, int end) {
        vector<vector<int>> adjacency_list(n);
        for (vector<int> edge : edges) {
            adjacency_list[edge[0]].push_back(edge[1]);
            adjacency_list[edge[1]].push_back(edge[0]);
        }
        
        stack<int> st;
        st.push(start);
        vector<bool> seen(n);
        
        while (!st.empty()) {
            // Get the current node.
            int node = st.top();
            st.pop();
            
            // Check if we have reached the target node.
            if (node == end) {
                return true;
            }
            
            // Check if we've already visited this node.
            if (seen[node]) {
                continue;
            }
            seen[node] = true;
            
            // Add all neighbors to the stack.
            for (int neighbor : adjacency_list[node]) {
                st.push(neighbor);
            }
        }
        
        return false;
    }
};

### 2. All Paths From Source to Target


#### 作法 C

// Meta knowledge of this problem: 
// The maximum possible size for the one notorious test case is 6208
#define MAX_SIZE 6208 

// The constraints given state that all elements of graph[i] are unique and no
// self-loop So the check visited can be skipped
void dfs(int** graph, int i, int** curr, int* currSize, int** answer, int graphSize, int *graphColSize, int *returnSize, int** returnColumnSizes) {
    (*currSize)++;
    (*curr)[(*currSize)-1] = i;
    if (i == graphSize - 1) // Reach target, here is graphSize-1;
    {
        // Store answer
        (*returnSize)++;
        answer[*returnSize - 1] = malloc(sizeof(int) * (*currSize));
        for (int i = 0; i < *currSize; ++i)
        {
            answer[*returnSize - 1][i] = (*curr)[i];
        }
        // Store answer size
        (*returnColumnSizes)[*returnSize - 1] = *currSize;
    }
    else
    {
        for (int j = 0; j < graphColSize[i]; ++j)
        {
            dfs(graph, graph[i][j], curr, currSize, answer, graphSize, graphColSize, returnSize, returnColumnSizes);
        }
    }
    (*currSize)--; // Back to previous node for next call
}
int **allPathsSourceTarget(int** graph, int graphSize, int* graphColSize, int* returnSize, int** returnColumnSizes) {
    // Initialize the 'answer' array assuming having the maximum size.
    int** answer = malloc(MAX_SIZE*sizeof(int *)); 
    
    // Assuming the answer having maximum size
    *returnColumnSizes = malloc(MAX_SIZE * sizeof(int)); 
    int* curr = calloc(graphSize, sizeof(int));    
    
    // For temporary tracking of answer    
    int currSize = 0; 
    *returnSize = 0;
    
    // Begin the DFS search;
    dfs(graph, 0, &curr, &currSize, answer, graphSize, graphColSize, returnSize, returnColumnSizes); 
    
    // returnSize is updated after the DFS finished
    // Trimming arrays to exact size
    
    // Trim to exact size;
    answer = realloc(answer, sizeof(int*) * (*returnSize)); 
    // Trim to exact size;
    *returnColumnSizes = realloc(*returnColumnSizes, sizeof(int) * (*returnSize)); 
    
    free(curr);
    return answer;
}

#### 作法 C++

class Solution {
public:
    // DFS
    void dfs(vector<vector<int>>& graph, int node, vector<int>& path, vector<vector<int>>& paths) {
        path.push_back(node);
        if (node == graph.size() - 1) {
            paths.emplace_back(path);
            return;
        }
        vector<int> nextNodes = graph[node];
        for (int nextNode : nextNodes) {
            dfs(graph, nextNode, path, paths);
            path.pop_back();
        }
    }

    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> paths;
        if (graph.size() == 0) {
            return paths;
        }
        vector<int> path;
        dfs(graph, 0, path, paths);
        return paths;
    }
};

## :memo: Reconstruct Itinerary (Hard)
**Overview**
Overall, we could consider this problem as a **graph traversal** problem, where an airport can be viewed as a vertex in graph and flight between airports as an edge in graph.


We would like to make a few clarification on the input of the problem, since it is not clear in the description of the problem.

As one might notice in the above example, the input graph is NOT what we call a **DAG** (Directed Acyclic Graph), since we could find at least a cycle in the graph.

In addition, the graph could even have some duplicate edges (i.e. we might have multiple flights with the same origin and destination).


**Input:** tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
**Output:** ["JFK","ATL","JFK","SFO","ATL","SFO"]
**Explanation:** Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.
Return the itinerary that has the smallest lexical order when read as a single string.
must use all the tickets once and only once.

### 作法

class Solution {
public:
    map<string, multiset<string>> targets;
    vector<string> route;
    
    void visit(string airport) {
        while (targets[airport].size()) {
            string next = *targets[airport].begin();
            targets[airport].erase(targets[airport].begin());
            visit(next);
        }
        route.push_back(airport);
    }
    
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (auto ticket : tickets)
            targets[ticket[0]].insert(ticket[1]);
        visit("JFK");
        return vector<string>(route.rbegin(), route.rend());  //reverse of route
    }    
};

### 延伸: code interview
https://www.youtube.com/watch?v=qz9tKlF431k&ab_channel=Cl%C3%A9mentMihailescu
影片的最後一個if應該是
if(who[i]==i&&deg[i]==0&&i **!=** who[mp[startingAirport]])

## :memo: All Paths from Source Lead to Destination (Medium)
檢查是否所有路都抵達destination，有可能會抵達別的點兒那個點沒有out-degree，或是具有cycle

**Input:** n = 4, edges = [[0,1],[0,3],[1,2],[2,1]], source = 0, destination = 3
**Output:** false
**Explanation:** We have two possibilities: to end at node 3, or to loop over node 1 and node 2 indefinitely.

### 作法
利用白灰黑去記錄點目前的state再利用DFS用跑整張圖
白:沒拜訪過的點
灰:已經處理過的點
黑:已經處理過的點且他的後代節點也已經處理

class Solution {
public:    
    bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
        int White = 0;
        int Gray = 1; // Vertex is being processed 
        int Black = 2; // Vertex and all its descendants are processed.
        
        vector<vector<int>> adjacency_list(n);
        vector<int> colors(n, White);
        
        for (vector<int> edge : edges) {
            adjacency_list[edge[0]].push_back(edge[1]);
        }
        
        stack<int> st;
        st.push(source);       
        
        while (!st.empty()) {
            int node = st.top();
            if (colors[node] == Gray) {
                st.pop();
                colors[node] = Black;
            } else if (adjacency_list[node].size() == 0) {
                if (node != destination) {
                    return false;
                }
                else {
                    st.pop();
                }
            } else {
                colors[node] = Gray;
                for(auto adj : adjacency_list[node]) {
                    if (colors[adj] == Gray) { // Cycle detected
                        return false;
                    }
                    if (colors[adj] == White) { // Unvisited node
                        st.push(adj);
                    }
                }
            }
        }
        
        return true;
    }
};

## :memo: Accounts Merge (Medium)


### 作法 Depth First Search (DFS)
In the worst case, **all the emails will end up belonging to a single person**.
Here **N** is the number of accounts and **K** is the maximum length of an account.
**時間:O(NKlogNK)**
**空間:O(NK)**

class Solution {
public:
    unordered_set<string> visited;
    unordered_map<string, vector<string>> adjacent;
    
    void dfs(vector<string>& mergedAccount, string& email) {
        visited.insert(email);

        mergedAccount.push_back(email);

        for (string& neighbor : adjacent[email]) {
            if (visited.find(neighbor) == visited.end()) {
                dfs(mergedAccount, neighbor);
            }
        }
    }

    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int accountsSize = accounts.size();

        for (vector<string>& account : accounts) {
            int accountSize = account.size();

            string accountFirstEmail = account[1];
            for (int j = 2; j <accountSize; j++) {
                string email = account[j];
                adjacent[accountFirstEmail].push_back(email);
                adjacent[email].push_back(accountFirstEmail);
            }
        }

        vector<vector<string>> mergedAccounts;
        for (vector<string>& account : accounts) {
            string accountName = account[0];
            string accountFirstEmail = account[1];

            if (visited.find(accountFirstEmail) == visited.end()) {
                vector<string> mergedAccount;

                mergedAccount.push_back(accountName);
                dfs(mergedAccount, accountFirstEmail);

                sort(mergedAccount.begin() + 1, mergedAccount.end());
                mergedAccounts.push_back(mergedAccount);
            }
        }

        return mergedAccounts;
    }
};

### 作法 Disjoint Set Union (DSU)
We are also sorting the components and the worst case will be when **all emails end up belonging to the same component** this will cost O(NK(log⁡NK))).
Here **N** is the number of accounts and **K** is the maximum length of an account.
**時間:O(NKlogNK)**
**空間:O(NK)**

class DSU {
public:
    vector<int> representative;
    vector<int> size;
    
    DSU(int sz) : representative(sz), size(sz) {
        for (int i = 0; i < sz; ++i) {
            // Initially each group is its own representative
            representative[i] = i;
            // Intialize the size of all groups to 1
            size[i] = 1;
        }
    }
    
    // Finds the representative of group x
    int findRepresentative(int x) {
        if (x == representative[x]) {
            return x;
        }
        
        // This is path compression
        return representative[x] = findRepresentative(representative[x]);
    }
    
    // Unite the group that contains "a" with the group that contains "b"
    void unionBySize(int a, int b) {
        int representativeA = findRepresentative(a);
        int representativeB = findRepresentative(b);
        
        // If nodes a and b already belong to the same group, do nothing.
        if (representativeA == representativeB) {
            return;
        }
        
        // Union by size: point the representative of the smaller
        // group to the representative of the larger group.
        if (size[representativeA] >= size[representativeB]) {
            size[representativeA] += size[representativeB];
            representative[representativeB] = representativeA;
        } else {
            size[representativeB] += size[representativeA];
            representative[representativeA] = representativeB;
        }
    }
};

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accountList) {
        int accountListSize = accountList.size();
        DSU dsu(accountListSize);
        
        // Maps email to their component index
        unordered_map<string, int> emailGroup;
        
        for (int i = 0; i < accountListSize; i++) {
            int accountSize = accountList[i].size();

            for (int j = 1; j < accountSize; j++) {
                string email = accountList[i][j];
                string accountName = accountList[i][0];
                
                // If this is the first time seeing this email then
                // assign component group as the account index
                if (emailGroup.find(email) == emailGroup.end()) {
                    emailGroup[email] = i;
                } else {
                    // If we have seen this email before then union this
                    // group with the previous group of the email
                    dsu.unionBySize(i, emailGroup[email]);
                }
            }
        }
    
        // Store emails corresponding to the component's representative
        unordered_map<int, vector<string>> components;
        for (auto emailIterator : emailGroup) {
            string email = emailIterator.first;
            int group = emailIterator.second;
            components[dsu.findRepresentative(group)].push_back(email);
        }

        // Sort the components and add the account name
        vector<vector<string>> mergedAccounts;
        for (auto componentIterator : components) {
            int group = componentIterator.first;
            vector<string> component = {accountList[group][0]};
            component.insert(component.end(), componentIterator.second.begin(), 
                             componentIterator.second.end());
            sort(component.begin() + 1, component.end());
            mergedAccounts.push_back(component);
        }
        
        return mergedAccounts;
    }
};

## :memo: *Is Graph Bipartite? (Medium)


### 作法 Coloring by Depth-First Search

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, -1);

        for (int start = 0; start < n; start++) {
            if (color[start] == -1) {
                stack<int> stk;
                stk.push(start);
                color[start] = 0;

                while (!stk.empty()) {
                    int node = stk.top();
                    stk.pop();

                    for (int neigh : graph[node]) {
                        if (color[neigh] == -1) {
                            stk.push(neigh);
                            color[neigh] = color[node] ^ 1;
                        } else if (color[neigh] == color[node]) {
                            return false;
                        }
                    }
                }
            }
        }

        return true;
    }
};

## :memo: 三、Breadth-First Search Algorithm
### Comparision with DFS
* The “depth-first search” algorithm can find the shortest path between two vertices in a “graph” with equal and positive weights but it must traverse all paths between two vertices before finding the shortest one.
* The “breadth-first search” algorithm, in most cases, can find the shortest path without traversing all paths.

### why?
* This is because when using "breadth-first search", as soon as a path between the source vertex and target vertex is found, it is guaranteed to be the shortest path between the two nodes.

### the primary use cases:
* Traversing **all vertices** in the “graph”.
* **layer by layer**,利用Queue去儲存neighbor並pop出queue的top，只有visited=0的要去找neighbor放進queue.
* **Finding the shortest path between two vertices in a graph where all edges have equal and positive weights**.
* 關鍵在於要將run過的路線記錄儲存在Queue中例如:A-B-C整條放入stack，然後如搜尋整張圖一樣跑演算法，當找到終點時(此條為最短路徑)，若繼續則可以找其他不是最短的路徑，若最短路徑為top則所有路徑都找到

### 1. Find if Path Exists in Graph

**Input:** n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
**Output:** true
**Explanation:** There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2

#### 作法 C++

class Solution {  // BFS
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        // construct adjacency list
        vector<vector<int>> adjacency_list(n);
        for (vector<int> edge : edges) {
            adjacency_list[edge[0]].push_back(edge[1]);
            adjacency_list[edge[1]].push_back(edge[0]);
        }
        
        // initial a queue and push start int queue
        queue<int> q;
        q.push(source);
        
        // initial a visited recording vector and 
        // mark start as true int the beginning
        vector<bool> visited(n);
        visited[source] = true;
        
        // do BFS process
        while (!q.empty()) {
            // pick up the front node in the queue 
            int node = q.front();
            q.pop();
            
            // check if the destination node
            if (node == destination) {
                return true;
            }
            
            // push the neighbors of the front node into the queue
            for (int neighbor : adjacency_list[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        
        return false;
    }
};

### 2. All Paths From Source to Target


#### 作法 C++

class Solution { // BFS
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> paths;
        if (graph.size() == 0) {
            return paths;
        }
        
        vector<int> path;
        queue<vector<int>> q;
        path.push_back(0);
        q.push(path);
        
        while (!q.empty()) {
            vector<int> currentPath = q.front();
            q.pop();
            int node = currentPath.back();
            for (int nextNode : graph[node]) {
                vector<int> tmpPath(currentPath.begin(), currentPath.end());
                tmpPath.push_back(nextNode);
                if (nextNode == graph.size() - 1) {
                    paths.push_back(tmpPath);
                } else {
                    q.push(tmpPath);
                }
            }
        }
        
        return paths;
    }
};

## :memo: Shortest Path in Binary Matrix (Medium)
return the length of the shortest clear path in the matrix


### 作法
matrix的標準做法，利用方向 **direction[8][2]** 去做**BFS**

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        int ans = 0;
        int direction[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        queue<pair<int, int>> q;
        vector<vector<bool>> visited(row, vector(col, false));
        
        if (grid[0][0] == 1 || grid[row - 1][col - 1] == 1) {
            return -1;
        }
        
        q.push(make_pair(0, 0));
        visited[0][0] = true;
        
        while (!q.empty()) {
            int steps = q.size();
            ans++;
            
            for (int i = 0; i < steps; i++) {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                if (x == row - 1 && y == col - 1) {
                    return ans;
                }
                
                for (int j = 0; j < 8; j++) {
                    int x1 = x + direction[j][0];
                    int y1 = y + direction[j][1];
                    if (x1 >= 0 && x1 < row && y1 >= 0 && y1 < col) {
                        if (!visited[x1][y1] && !grid[x1][y1]) {
                            q.push(make_pair(x1, y1));
                            visited[x1][y1] = true;
                        }
                    }
                }
            }
        }
        
        return -1;
    }
};

## :memo: Rotting Oranges (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**.



### 作法
這題要找的是layer的層數，一樣是matrix標準作法，direction和BFS，不過要用兩層while去算layer數，while的內容也要調整

class Solution {
public:    
    int orangesRotting(vector<vector<int>>& grid) {
        int direction[4][2] = {{0, 1}, {-1, 0}, {1, 0}, {0, -1}};
        int layer = -1;
        
        queue<pair<int,int>> q;
        
        for (int row = 0; row < grid.size(); row++) {
            for (int col = 0; col< grid[0].size(); col++) {
                if (grid[row][col] == 2) {
                    q.push({row,col});
                }
            }
        }

        while (!q.empty()) {
            queue<pair<int,int>> temp;
            temp = q;
            
            while (!temp.empty()) {
                for (int r = 0; r < 4; r++) {
                    int x = q.front().first;
                    int y = q.front().second;
                    int x1 = x + direction[r][0];
                    int y1 = y + direction[r][1];
                    // cout<<x<<' '<<y<<endl;
                    if (x1 < grid.size() && x1 >= 0 && y1 < grid[0].size() && y1 >= 0) {
                        if (grid[x1][y1] == 1) {
                            grid[x1][y1] = 2;
                            q.push({x1, y1}); 
                            // cout<<x1<<' '<<y1<<endl;
                        }
                    }                    
                }
                temp.pop();
                q.pop();                
            }
            
            layer++;           
        }
            
        for (int row = 0; row < grid.size(); row++) {
            for (int col = 0; col < grid[0].size(); col++) {
                if (grid[row][col] == 1) {
                    return -1;
                }
            }
        }
            
        return max(0, layer);
    }
};

## :memo: 四、Minimum Spanning Tree
### Spanning tree

### Minimum spanning tree
a “weighted undirected graph” can have multiple minimum spanning trees.

### Learn:
* the cut property
* two algorithms for constructing a “minimum spanning tree”:
* **Kruskal’s Algorithm**
* **Prim’s algorithm**

## :memo: Cut Property
Graph with a cut
* First, in Graph theory, a “cut” is a partition of vertices in a “graph” into two disjoint subsets.
Figure 11 illustrates a “cut”, where (B, A, E) forms one subset, and (C, D) forms the other subset.
* Second, a crossing edge is an edge that connects a vertex in one set with a vertex in the other set.
In Figure 11, (B, C), (A, C), (A, D), (E, D) are all “crossing edges”.

For any cut C of the graph, if the weight of an edge E in the cut-set of C is strictly smaller than the weights of all other edges of the cut-set of C, then this edge belongs to all MSTs of the graph.

## :memo: Kruskal’s Algorithm
“Kruskal’s algorithm” is an algorithm to construct a “minimum spanning tree” of a “weighted undirected graph”.

步驟:
1. 依升序排序所有邊
2. 並依序增加邊到最小生成數，會產生cycle的邊不要增加
3. 重複步驟1,步驟2直到最小生成樹為N-1條邊

## :memo: Min Cost to Connect All Points (Kruskal's Algotithm)

### 作法
利用Kruskal's Algotithm並且用union來偵測cycle

class UnionFind {
public:
    vector<int> group;
    vector<int> rank;

    UnionFind(int size) {
        group = vector<int>(size);
        rank = vector<int>(size);
        for (int i = 0; i < size; ++i) {
            group[i] = i;
        }
    }

    int find(int node) {
        if (group[node] != node) {
            group[node] = find(group[node]);
        }
        return group[node];
    }

    bool join(int node1, int node2) {
        int group1 = find(node1);
        int group2 = find(node2);
        
        // node1 and node2 already belong to same group.
        if (group1 == group2) {
            return false;
        }

        if (rank[group1] > rank[group2]) {
            group[group2] = group1;
        } else if (rank[group1] < rank[group2]) {
            group[group1] = group2;
        } else {
            group[group1] = group2;
            rank[group2] += 1;
        }

        return true;
    }
};

class Solution {
public:
    int manh_dis(vector<int> pointA, vector<int> pointB) {
        return abs(pointA[0] - pointB[0]) + abs(pointA[1] - pointB[1]);
    }
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        vector<pair<int, pair<int, int>>> allEdges;
        
        for (int i = 0; i < points.size() ; i++) {
            for (int j = i + 1; j < points.size() ;j++) {
                allEdges.push_back(make_pair(manh_dis(points[i], points[j]), make_pair(i, j)));
            }            
        }
        
        sort(allEdges.begin(), allEdges.end());
        
        // for (pair<int, pair<int, int>> p : allEdges) {
        //     cout<<p.first;
        //     cout<<"\t";
        //     cout<<"["<<p.second.first<<","<<p.second.second<<"]";            
        //     cout<<endl;
        // }
        
        UnionFind uf(n);
        int mstCost = 0;
        int edgesUsed = 0;
        
        for (int i = 0; i < allEdges.size() && edgesUsed < n - 1; ++i) {
            int node1 = allEdges[i].second.first;
            int node2 = allEdges[i].second.second;
            int weight = allEdges[i].first;
            
            if (uf.join(node1, node2)) { // key point : detect cycle !!!
                mstCost += weight;
                edgesUsed++;
            }
        }
        
        return mstCost;
    }
};

## :memo: Prim’s Algorithm
步驟:
1. 添加最近鄰居到最小生成樹並標為visited
2. 若成為cycle則不添加
3. 重複步驟1,步驟2直到最小生成樹為N-1條邊

## :memo: The difference between Kruskal and Prim
* **“Kruskal’s algorithm”** expands the “minimum spanning tree” **by adding edges**.
* **“Prim’s algorithm”** expands the “minimum spanning tree” **by adding vertices**.

## :memo: Min Cost to Connect All Points (Prim’s Algorithm)

### 作法
利用Min-Heap執行Prim’s Algorithm

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        
        // Min-heap to store minimum weight edge at top.
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
        
        // Track nodes which are include in MST.
        vector<bool> inMST(n);
        
        heap.push({0, 0});
        int mstCost = 0;
        int edgeUsed = 0;
        
        while (edgeUsed < n) {
            pair<int, int> topElement = heap.top();
            heap.pop();
            
            int weight = topElement.first;
            int currNode = topElement.second;
            
            // If node was already includes in MST we will discard this edge.
            if (inMST[currNode]) {
                continue;
            }
            
            inMST[currNode] = true;
            mstCost += weight;
            edgeUsed++;
            
            for (int nextNode = 0; nextNode < n; ++nextNode) {
                // If next node is not in MST, then edge from curr node
                // to next node can be pushed in the priority queue
                if (!inMST[nextNode]) {
                    int nextWeight = abs(points[currNode][0] - points[nextNode][0]) +
                                     abs(points[currNode][1] - points[nextNode][1]);
                    
                    heap.push({nextWeight, nextNode});
                }
            }
        }
        
        return mstCost;
    }
};

## :memo: 五、Single Source Shortest Path
the **“breadth-first search”** algorithm can **only** solve the “shortest path” problem in **“unweighted graphs”**. But, we often need to **find the “shortest path” in a “weighted graph”**.

### Edge Relaxation
imagine that each path is a rubber band of length 1.
The original path from A to D is of length 3, so the rubber band was stretched to 3 times its original length.
When we relax the path to length 2, by visiting C first, the rubber band is now only stretched to twice its length, so you can imagine the rubber band being relaxed, hence the term edge relaxation.

### Two “single source shortest path” algorithms
* Dijkstra’s algorithm:
solve the “single-source shortest path” in a weighted directed graph only with non-negative weights.

* Bellman-Ford algorithm:
solve the “single-source shortest path” in a weighted directed graph with any weights, including, of course, negative weights.

## :memo: Dijkstra's Algorithm

### The Main Idea
We take the starting point u as the center and gradually expand outward while updating the “shortest path” to reach other vertices.

“Dijkstra's Algorithm” uses a “greedy approach”. Each step selects the “minimum weight” from the currently reached vertices to find the “shortest path” to other vertices.

### Proof of the Algorithm

### Limitation of the Algorithm
* Weights of all edges are non-negative.


## :memo: Network Delay Time (Medium)
times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.



### 作法
利用Dijkstra's Algorithm找抵達所有點的時間後取最大值，一開始所有點的抵達時間皆為無窮大，隨著演算法執行會縮小

class Solution {
public:
    // Adjancy list, defined it as per the maximum number of nodes
    // But can be defined with input size as well
    vector<pair<int, int>> adj[101];
    
    void dijkstra(vector<int>& signalReceivedAt, int source, int n) {
        priority_queue<pair<int, int>, vector<pair<int, int>>,
        greater<pair<int, int>>> pq;
        pq.push({0, source});
        
        // Time for starting node is 0
        signalReceivedAt[source] = 0;
        
        while (!pq.empty()) {
            int currNodeTime = pq.top().first;
            int currNode = pq.top().second;
            pq.pop();
            
            if (currNodeTime > signalReceivedAt[currNode]) {
                continue;
            }
            
            // Broadcast the signal to adjacent nodes
            for (pair<int, int> edge : adj[currNode]) {
                int time = edge.first;
                int neighborNode = edge.second;
                
                // Fatest signal time for neighbor so far
                // signalReceivedAt[currNode] + time
                // time when signal reaches neighborNode
                if (signalReceivedAt[neighborNode] > currNodeTime + time) {
                    signalReceivedAt[neighborNode] = currNodeTime + time;
                    pq.push({signalReceivedAt[neighborNode], neighborNode});
                }
            }
        }
    }
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        // Build the adjacency list
        for (vector<int> time : times) {
            int source = time[0];
            int dest = time[1];
            int travelTime = time[2];
            
            adj[source].push_back({travelTime, dest});
        }
        
        vector<int> signalReceivedAt(n + 1, INT_MAX);
        dijkstra(signalReceivedAt, k, n);
        
        int answer = INT_MIN;
        for (int i = 1; i <= n; i++) {
            answer = max(answer, signalReceivedAt[i]);
        }
        
        // INT_MAX signifies atleat one node is unreachable
        return answer == INT_MAX ? -1 : answer;
    }
};

## :memo: Bellman Ford Algorithm
### Basic Theorem
* Theorem 1: In a “graph with no negative-weight cycles” with N vertices, the shortest path between any two vertices has at most N-1 edges.


* Theorem 2: In a “graph with negative weight cycles”, there is no shortest path.


### Using Dynamic Programming to Find the Shortest Path
第一回合:用一條邊到達的距離
第二回合:更新是否從其他非來源點能縮短總距離並更新
第三回合:到N-1條便結束

### Limitation of the algorithm
* “Bellman-Ford algorithm” is only applicable to “graphs” with no “negative weight cycles”.

### How does the Bellman-Ford algorithm detect “negative weight cycles”?
* After relaxing each edge N-1 times, perform the Nth relaxation. According to the “Bellman-Ford algorithm”, all distances must be the shortest after relaxing each edge N-1 times. However, after the Nth relaxation, if there exists **distances[u] + weight(u, v) < distances(v) for any edge(u, v)**, it means there is a shorter path . At this point, we can conclude that there exists a “negative weight cycle”.

### Complexity Analysis
V represents the number of vertices, and E represents the number of edges.

Time Complexity:
We iterate through all the vertices, and in each iteration, we'll perform a relaxation operation for each appropriate edge.
Therefore, the time complexity would be O(V⋅E).

Space Complexity:
O(V).
We use two arrays of length VV. One to store the shortest distance from the source vertex using at most k-1 edges.
The other is to store the shortest distance from the source vertex using at most k edges.

## :memo: Improved Bellman-Ford Algorithm with Queue — SPFA Algorithm

* The improvement is that for a graph without negative cycles, after relaxing each edge N-1 times, we can get the minimum distance from the starting vertex to all other vertices.
* However, there could be unnecessary computation when relaxing all edges N-1 times, resulting in suboptimal time complexity in some cases.
* This improvement is known as “the Shortest Path Faster Algorithm” (SPFA algorithm).
* Instead of choosing among any untraversed edges, as one does by using the “Bellman-Ford” algorithm, the “SPFA” Algorithm uses a “queue” to maintain the next starting vertex of the edge to be traversed.
* **Only when the shortest distance of a vertex is relaxed and that the vertex is not in the “queue”, we add the vertex to the queue.**
* We iterate the process until the queue is empty. At this point, we have calculated the minimum distance from the given vertex to any vertices.

### Complexity Analysis
V represents the number of vertices, and E represents the number of edges.

Time Complexity:
We iterate through all the vertices, and in each iteration, we'll perform a relaxation operation for each appropriate edge.
Therefore, the time complexity would be O(V⋅E).

Space Complexity:
O(V).
We need to store V vertices.

## :memo: Cheapest Flights Within K Stops (Medium)
flights[i] = [fromi, toi, pricei]
Return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.



### 作法 C++

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        // Bellman-Ford implementation
        int MAX_VALUE = 100000;
        vector<int> prices(n, MAX_VALUE);
        prices[src] = 0;
        
        for (int i = 0; i < k + 1; i++) {
            vector<int> tmpPrices = prices; // use tmpPrices as a place to update the most recent iteration of i
            for (const auto& flight : flights) {
                tmpPrices[flight[1]] = min(tmpPrices[flight[1]], flight[2] + prices[flight[0]]);
            }
            prices = tmpPrices;
        }
        
        return  prices[dst] == MAX_VALUE ? -1 : prices[dst];
    }
};

## :memo: Path With Minimum Effort (Medium)
Return the minimum effort required to travel from the top-left cell to the bottom-right cell.



### 作法
Matrix標準作法directions，執行Bellman Ford演算法

class Solution {
public:
    class Cell {
    public:
        int x, y;
        int difference;
        Cell(int x, int y, int difference) {
            this->x = x;
            this->y = y;
            this->difference = difference;
        }
    };
    
    struct Comparator {
        bool operator()(Cell const &p1, Cell const &p2) {
            return p2.difference < p1.difference;
        }
    };
    
    bool isValidCell(int x, int y, int row, int col) {
        return x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1;
    }
    
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int minimumEffortPath(vector<vector<int>>& heights) {
        int row = heights.size();
        int col = heights[0].size();
        vector<vector<int>> differenceMatrix(row, vector<int>(col, INT_MAX));
        differenceMatrix[0][0] = 0;
        priority_queue<Cell, vector<Cell>, Comparator> queue;
        vector<vector<bool>> visited(row, vector<bool>(col, false));
        queue.push(Cell(0, 0, differenceMatrix[0][0]));
        while (!queue.empty()) {
            Cell curr = queue.top();
            queue.pop();
            visited[curr.x][curr.y] = true;
            if (curr.x == row - 1 && curr.y == col - 1) return curr.difference;
            for (auto direction : directions) {
                int adjacentX = curr.x + direction[0];
                int adjacentY = curr.y + direction[1];
                if (isValidCell(adjacentX, adjacentY, row, col) && !visited[adjacentX][adjacentY]) {
                    int currentDifference = abs(heights[adjacentX][adjacentY] - heights[curr.x][curr.y]);
                    int maxDifference = max(currentDifference,differenceMatrix[curr.x][curr.y]);
                    if (differenceMatrix[adjacentX][adjacentY] > maxDifference) {
                        differenceMatrix[adjacentX][adjacentY] = maxDifference;
                        queue.push(Cell(adjacentX, adjacentY, maxDifference));
                    }
                }
            }
        }
        return differenceMatrix[row - 1][col - 1];
    }
};

## :memo: 六、Kahn's Algorithm
排修課順序演算法
關鍵在**degree的操作**

to take Course C, you need to complete Course B first, and to take Course B, you need to complete Course A first.

“Topological sorting” helps solve the problem. It provides a linear sorting based on the required ordering between vertices in directed acyclic graphs.
To be specific, given vertices u and v, to reach vertex v, we must have reached vertex u first. In “topological sorting”, u has to appear before v in the ordering.
The most popular algorithm for “topological sorting” is Kahn’s algorithm.

將in-degree=0的點(A)push到queue之中
pop出點A，並將其抵達點(B,C)減掉1個in-degree
將in-degree=0的點(A)push到queue之中
pop出點C，並將其抵達點(B,D)減掉1個in-degree
將in-degree=0的點(B)push到queue之中
pop出點B，並將其抵達點(D)減掉1個in-degree
將in-degree=0的點(D)push到queue之中
pop出點D，結束

### Limitation of the Algorithm
* “Topological sorting” only works with graphs that are directed and acyclic.
* There must be at least one vertex in the “graph” with an “in-degree” of 0. If all vertices in the “graph” have a non-zero “in-degree”, then all vertices need at least one vertex as a predecessor. In this case, no vertex can serve as the starting vertex.

## :memo: Course Schedule (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.


### 作法 Kahn's Algorithm

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> indegree(numCourses);
        vector<vector<int>> adj(numCourses);
        for (auto prerequisite : prerequisites) {
            adj[prerequisite[1]].push_back(prerequisite[0]);
            indegree[prerequisite[0]]++;
        }

        queue<int> q;

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

        int nodesVisited = 0;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            nodesVisited++;

            for (auto& neighbor : adj[node]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        return nodesVisited == numCourses;
    }
};

## :memo: Course Schedule II (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 the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.


### 作法 Kahn's Algorithm

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> result(numCourses);
        if (numCourses == 0) {
            return result;
        }
        
        if (prerequisites.empty()) {
            for (int i = 0; i < numCourses; i++) {
                result[i] = i;
            }
            return result;
        }
        
        vector<int> indegree(numCourses);
        queue<int> zeroDegree;
        for (vector<int>& pre : prerequisites) {
            indegree[pre[0]]++;
        }
        for (int i = 0; i < indegree.size(); i++) {
            if (indegree[i] == 0) {
                zeroDegree.push(i);
            }
        }
        if (zeroDegree.empty()) {
            return vector<int>();
        }
        
        int index = 0;
        while (!zeroDegree.empty()) {
            int course = zeroDegree.front();
            zeroDegree.pop();
            result[index] = course;
            index++;
            for (vector<int>& pre : prerequisites) {
                if (pre[1] == course) {
                    indegree[pre[0]]--;
                    if (indegree[pre[0]] == 0) {
                        zeroDegree.push(pre[0]);
                    }
                }
            }
        }
        
        for (int in : indegree) {
            if (in != 0) {
                return vector<int>();
            }
        }
        
        return result;
    }
};

## :memo: Alien Dictionary (Hard)
There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them.

A string s is lexicographically smaller than a string t if at the first letter where they differ, the letter in s comes before the letter in t in the alien language. If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length.


### 作法
看完題目要想到Kahn's Algorithm有點難度

class Solution {
public:
    string alienOrder(vector<string>& words) {
        if (words.size() == 0) return "";
        unordered_map<char, int> indegree;
        unordered_map<char, unordered_set<char>> graph;
        
        // initialize
        for (int i = 0; i < words.size(); i++) {
            for (int j = 0; j < words[i].size(); j++) {
                char c = words[i][j];
                indegree[c] = 0;
            }
        }
        
        // build graph and record indegree
        for (int i = 0; i < words.size() - 1; i++) {
            string cur = words[i];
            string nex = words[i + 1];
            int len = min(cur.size(), nex.size());
            for (int j = 0; j < len; j++) {
                if (cur[j] != nex[j]) {
                    unordered_set<char> set = graph[cur[j]];
                    if (set.find(nex[j]) == set.end()) {
                        graph[cur[j]].insert(nex[j]);   // build graph
                        indegree[nex[j]]++; // add indegree
                    }
                    break;
                }
                if (j == len - 1 and cur.size() > nex.size()) return "";    // This solution fails for new test cases like ["abc" "ab"] by giving a wrong output of "cab" instead of "" .
            }
        }
        
        // topological sort
        string ans;
        queue<char> q;
        for (auto& e : indegree) {
            if (e.second == 0) {
                q.push(e.first);
            }
        }
        while (!q.empty()) {
            char cur = q.front();
            q.pop();
            ans += cur;
            
            if (graph[cur].size() != 0) {
                for (auto& e : graph[cur]) {
                    indegree[e]--;
                    if (indegree[e] == 0) {
                        q.push(e);
                    }
                }
            }
        }
        
        // tell if it is cyclic
        return ans.length() == indegree.size() ? ans : "";
    }
};

## :memo: Minimum Height Trees (Medium)
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 idea is that we trim out the leaf nodes layer by layer, until we reach the core of the graph, which are the centroids nodes.


### 作法
從leaf往中間靠

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        vector<int> indegree(n, 0);    //vector<int> indegree keeps count of the number nodes approaching a node
        vector<int> ans;
        for (auto &e : edges) {     //Creating an adjacency matrix for the given graph
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
            indegree[e[0]]++;
            indegree[e[1]]++;
        }
        
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 1) {     //add all the leaf nodes to the queue
                q.push(i);
                indegree[i]--;  
            }
        }
        
        while (!q.empty()) {
            int s = q.size();
            ans.clear();
            for (int i = 0; i < s; i++) {
                int curr = q.front();
                q.pop();
                ans.push_back(curr);
                for (auto child : graph[curr]) {    //For each node, attached to the leaf nodes, we decrement the indegree i.e remove the leaf nodes connected to them. We keep on doing this until we reach the middle nodes.
                    indegree[child]--;
                    if (indegree[child] == 1) {
                        q.push(child);
                    }                    
                }
            }
        }
        
        if (n == 1) {
            ans.push_back(0);   //If there is only 1 node in the graph, the min height is 0, with root being '0' 
        }
        
        return ans;        
    }
};

## :memo: Parallel Courses (Medium)
Return the minimum number of semesters needed to take all courses. If there is no way to take all the courses, return -1.





### 作法
利用BFS去做學習並追蹤in-degree的數量，要用到nextQueue去暫存endNode給下一個學習Queue(學期)pop用，每從bfsQueue出來一個node便加1學期數

class Solution {
public:
    int minimumSemesters(int n, vector<vector<int>>& relations) {
        vector<int> inCount(n + 1, 0);  // or indegree
        vector<vector<int>> graph(n + 1);
        for (auto& relation : relations) {
            graph[relation[0]].push_back(relation[1]);
            inCount[relation[1]]++;
        }
        int step = 0;
        int studiedCount = 0;
        vector<int> bfsQueue;
        for (int node = 1; node < n + 1; node++) {
            if (inCount[node] == 0) {
                bfsQueue.push_back(node);
            }
        }
        // start learning with BFS
        while (!bfsQueue.empty()) {
            // start new semester
            step++;
            vector<int> nextQueue;
            for (auto& node : bfsQueue) {
                studiedCount++;
                for (auto& endNode : graph[node]) {
                    inCount[endNode]--;
                    // if all prerequisite courses learned
                    if (inCount[endNode] == 0) {
                        nextQueue.push_back(endNode);
                    }
                }
            }
            bfsQueue = nextQueue;
        }
        
        return studiedCount == n ? step : -1;
    }
};

## :memo: 刷題檢討
find和union要會寫和用，有這些演算法方式:
1. Quick Find
2. Quick Union
3. Union by Rank
4. Path Compression Optimization
5. Optimized “disjoint set” with Path Compression and Union by Rank

從BFS開始都用C++寫，BFS以前有C的code可以複習。

找root and 合併:
* Disjoint Set
* Quick Find
* Quick Union

travel all nodes and find the shortest paths:
* DFS (Stack)
* BFS (Queue)

Minimum Spanning Tree:
* Kruskal's Algoritm (加邊)
* Prim's Algorithm (加點)

topology sort 排課程順序:
* Kahn's Algorithm (degree的操作)