class Solution {
    int n;
public:
    void bfs(const vector<vector<int>> & graph, priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> & pq, vector<int> & distance, vector<int> & visited, const int & node) {
        visited = vector<int>(n, 0);
        pq.emplace(0, node);
        visited[node] = 1;
        distance[node] = 0;

        while(!pq.empty()) {
            const auto [dist, cur] = pq.top();
            pq.pop();
            for(const auto & adj: graph[cur]) {
                if(distance[adj] > distance[cur] + 1) {
                    distance[adj] = distance[cur] + 1;
                    pq.emplace(distance[adj], adj);
                }
            }
        }
    }
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        n = edges.size();
        vector<vector<int>> graph(n);
        for(int i = 0; i < n; i++) {
            if(edges[i] == -1) continue;
            graph[i].emplace_back(edges[i]);
        }
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        vector<int> distance1(n, INT_MAX / 2);
        vector<int> distance2(n, INT_MAX / 2);
        vector<int> visited;

        bfs(graph, pq, distance1, visited, node1);
        bfs(graph, pq, distance2, visited, node2);

        // Get the distance. Then check the answer.
        int ans_dist = INT_MAX / 2;
        int ans = -1;

        for(int i = 0; i < n; i++) {
            int tmp_ans = max(distance1[i], distance2[i]);
            if(ans_dist > tmp_ans) {
                ans_dist = tmp_ans;
                ans = i;
            }
            else if(ans_dist == tmp_ans) {
                ans = min(ans, i);
            }
        }
        return ans == INT_MAX / 2 ? -1 : ans;
    }
};

class Graph {
    vector<vector<pair<int,int>>>graph;
    vector<int> visited;
    vector<int> distance;
    int n;
public:
    Graph(int n, vector<vector<int>>& edges) {
        graph = vector<vector<pair<int,int>>>(n);
        for(const auto & edge: edges) {
            int from = edge[0], to = edge[1], edgeCost = edge[2];
            graph[from].emplace_back(to, edgeCost);
        }
        Graph::n = n;
    }
    
    void addEdge(vector<int> edge) {
        int from = edge[0], to = edge[1], edgeCost = edge[2];
        graph[from].emplace_back(to, edgeCost);
    }
    
    int shortestPath(int node1, int node2) {
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        visited = vector<int>(n, 0);
        distance = vector<int>(n, INT_MAX / 2);
        pq.emplace(0, node1);
        distance[node1] = 0;
        while(!pq.empty()) {
            const auto [dist, cur] = pq.top();
            pq.pop();
            if(visited[cur]) continue;
            visited[cur] = 1;
            for(const auto & adj: graph[cur]) {
                const auto [adj_to, adj_w] = adj;
                if(distance[adj_to] > distance[cur] + adj_w) {
                    distance[adj_to] = distance[cur] + adj_w;
                    pq.emplace(distance[adj_to], adj_to);
                }
            }
        }
        return distance[node2] == INT_MAX / 2 ? -1 : distance[node2];
    }
};

/**
 * Your Graph object will be instantiated and called as such:
 * Graph* obj = new Graph(n, edges);
 * obj->addEdge(edge);
 * int param_2 = obj->shortestPath(node1,node2);
 */

constexpr int directions[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
class Solution {
public:
    int minTimeToReach(vector<vector<int>>& moveTime) {
        // [dist, x, y];
        priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<tuple<int,int,int>>> pq;
        pq.emplace(0, 0, 0);
        int rows = moveTime.size(), cols = moveTime[0].size();
        vector<vector<int>> distance(rows, vector<int>(cols, INT_MAX / 2));
        vector<vector<int>> visited(rows, vector<int>(cols, 0));
        distance[0][0] = 0;

        while(!pq.empty()) {
            const auto [dist, x, y] = pq.top();
            pq.pop();
            if(visited[x][y]) continue;
            visited[x][y] = 1;
            for(int i = 0; i < 4; i++) {
                int nx = x + directions[i][0], ny = y + directions[i][1];
                if(nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
                    int temp_distance = max(dist, moveTime[nx][ny]) + (x+y) % 2 + 1;
                    if(temp_distance < distance[nx][ny]) {
                        distance[nx][ny] = temp_distance;
                        pq.emplace(temp_distance, nx, ny);
                    }
                }
            }
        }
        return distance[rows - 1][cols - 1];
    }
};

class Solution {
public:
    int n;
    int CheckTransfer(int nums, vector<vector<int>> & board) {
        int row, col;
        if(nums % n == 0) {
            row = n - nums / n;
            if(row % 2 != n % 2) {
                col = n-1;
            }
            else {
                col = 0;
            }
        } else {
            row = n - 1 - nums / n;
            if(row % 2 != n % 2) {
                col = (nums % n) - 1;
            }
            else {
                col = n - (nums % n);
            }
        }
        
        // // ** debug **
        // cout << nums << " at: (" << row << " ," << col << ")\n";
        return board[row][col]; 
    }
    int snakesAndLadders(vector<vector<int>>& board) {
        // Build Matrix.
        n = board.size();

        vector<int> distance(n*n+1, INT_MAX / 2);
        vector<int> visited(n*n+1, 0);
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        pq.emplace(0,1);
        distance[1] = 0;
        while(!pq.empty()) {
            // BFS to get the adjacent point.
            const auto [dist, cur] = pq.top();
            pq.pop();
            if(visited[cur]) continue;
            visited[cur] = 1;
            for(int i = cur + 1; i <= min(cur + 6, n * n); i++) {
                int transfer = CheckTransfer(i, board);
                int adj = transfer == -1 ? i : transfer;
                if(distance[adj] > distance[cur] + 1) {
                    distance[adj] = distance[cur] + 1;
                    pq.emplace(distance[adj], adj);
                }
            }
        }
        return distance[n * n] == INT_MAX / 2 ? -1 : distance[n * n];
    }
};

class Solution {
public:
    int n;
    int CheckTransfer(int nums, vector<vector<int>> & board) {
        int row, col;
        if(nums % n == 0) {
            row = n - nums / n;
            if(row % 2 != n % 2) {
                col = n-1;
            }
            else {
                col = 0;
            }
        } else {
            row = n - 1 - nums / n;
            if(row % 2 != n % 2) {
                col = (nums % n) - 1;
            }
            else {
                col = n - (nums % n);
            }
        }
        
        // // ** debug **
        // cout << nums << " at: (" << row << " ," << col << ")\n";
        return board[row][col]; 
    }
    int snakesAndLadders(vector<vector<int>>& board) {
        // Build Matrix.
        n = board.size();

        vector<int> visited(n*n+1, 0);
        queue<pair<int,int>> q;
        q.emplace(1, 0);
        while(!q.empty()) {
            // BFS to get the adjacent point.
            const auto [cur, dist] = q.front();
            q.pop();
            visited[cur] = 1;
            for(int i = cur + 1; i <= min(cur + 6, n * n); i++) {
                int transfer = CheckTransfer(i, board);
                int adj = transfer == -1 ? i : transfer;
                if(visited[adj]) continue;
                if(adj == n * n) return dist + 1;
                visited[adj] = 1;
                q.emplace(adj, dist + 1);
            }
        }
        return -1;
    }
};

func distributeCandies(n int, limit int) int64 {
	var ans int64
	ans = 0
	for i := 0; i <= min(limit, n); i++ {
		ans = ans + int64(max(int64(min(limit, n-i)) - int64(max(n-i-limit, 0))+1, 0))
	}
	return ans
}

class Solution {
public:
    long long distributeCandies(int n, int limit) {
        long long ans = 0;
        for(int i = 0; i <= min(limit, n); i++) {
            ans += (long long)max(min(limit, n-i) - max(n-i-limit, 0) + 1, 0);
        }
        return ans;
    }
};

CONGA 观察到了 ECMP 在负载均衡方面的缺陷：

• 爆发大流时受限于哈希随机分配，碰撞概率增大导致负载不均衡。
• 仅关注局部信息而未关注到潜在下游通路的拥塞影响。
  导致了链路故障情况下即使有冗余也使得成功送达流量下降 40%。

并且，针对其他解决方案的不足：如中心化调度导致的数据中心场景下流量快速变化的反应不足，局部路由特性对全局掌握不佳，基于终端主机的传输层协议增加传输层复杂度并且无法控制绕开内核具有自身协议栈的高性能应用，提出了属于自己的方案：

• 分布式框架，允许在 RTT 尺度下进行拥塞反应。
• 全局拥塞信息控制，leaf-leaf 控制快速传输网络拥塞指标
• 独立于传输层的网络层部署，避免影响终端主机和引入复杂的传输层控制。

需要满足：高效性，传输层独立，不对称性稳定，可增量部署，可以针对 Leaf-spine 拓扑优化。

class Solution {
public:
    int candy(vector<int>& ratings) {
        // Two times iteration.
        vector<int> ans;
        int count = 1;
        ans.emplace_back(count++);
        for(int i = 1; i < ratings.size(); i++) {
            if(ratings[i] > ratings[i-1]) {
                ans.emplace_back(count++);
            }
            else {
                count = 1;
                ans.emplace_back(count++);
            }
        }
        

        #ifdef DEBUG
        cout << ans.size() << ' ' << ratings.size() << '\n';
        for(int i = 0; i < ans.size(); i++) {
            cout << ans[i] << ' ';
        }
        cout << '\n';
        #endif

        count = 1;
        for(int i = ratings.size() - 1; i > 0; i--) {
            if(ratings[i-1] > ratings[i]) {
                ans[i-1] = max(ans[i-1], ++count);
            }
            else {
                count = 1;
                ans[i-1] = max(ans[i-1], count);
            }
        }
        
        #ifdef DEBUG
        cout << ans.size() << ' ' << ratings.size() << '\n';
        for(int i = 0; i < ans.size(); i++) {
            cout << ans[i] << ' ';
        }
        cout << '\n';
        #endif

        return reduce(ans.begin(), ans.end());
    }
};

func candy(ratings []int) int {
	n := int(len(ratings))
	ans := make([]int, n)
	count := 1
	ans[0] = count
	count++

	for i := 1; i < n; i++ {
		if ratings[i-1] < ratings[i] {
			ans[i] = count
			count++
		} else {
			count = 1
			ans[i] = count
			count++
		}
	}

	count = 1
	for i := n - 1; i > 0; i-- {
		if ratings[i-1] > ratings[i] {
			count++
			ans[i-1] = max(ans[i-1], count)
		} else {
			count = 1
		}
	}
	var final int = 0
	for i := 0; i < n; i++ {
		final = final + ans[i]
	}
	return final
}

好麻烦的题目

class Solution {
    public:
        bool isPrintable(vector<vector<int>>& targetGrid) {
            // The tuple has color -> (up, down, left, right).
            unordered_map<int, tuple<int,int,int,int>> color_mat;

            // Find the tuple mat from the graph.
            for(int i = 0; i < targetGrid.size(); i++) {
                for(int j = 0; j < targetGrid[i].size(); j++) {
                    int color = targetGrid[i][j];
                    if(color_mat.find(color) == color_mat.end()) {
                        color_mat[color] = make_tuple(INT_MAX / 2, 0, INT_MAX / 2, 0);
                    }
                    const auto & [up, down, left, right] = color_mat[color];
                    color_mat[color] = make_tuple(min(up, i), max(down, i), min(left, j), max(right, j));
                }
            }

            // Search the matrix and find the topology order.
            unordered_map<int, unordered_set<int>> graph;
            unordered_map<int, int> inDegree;
            for(const auto & ele: color_mat) {
                const int & color = ele.first;
                const auto & [up, down, left, right] = ele.second;
                graph[color] = unordered_set<int>();
                if(inDegree.find(color) == inDegree.end()) {
                    inDegree[color] = 0;
                }
                for(int i = up; i <= down; i++) {
                    for(int j = left; j <= right; j++) {
                        if(targetGrid[i][j] != color && graph[color].find(targetGrid[i][j]) == graph[color].end()) {
                            graph[color].insert(targetGrid[i][j]);
                            inDegree[targetGrid[i][j]]++;
                        }
                    }
                }
            }
            
            int n = graph.size();
            queue<int> q;
            int count = 0;
            for(const auto & ele: inDegree) {
                if(ele.second == 0) {
                    q.emplace(ele.first);
                }
            }

            while(!q.empty()) {
                int cur = q.front();
                q.pop();
                count++;
                for(const auto & adj: graph[cur]) {
                    if(--inDegree[adj] == 0) {
                        q.emplace(adj);
                    }
                }
            }

            #ifdef DEBUG
            for(const auto & element: color_mat) {
                const auto & [u,d,l,r] = color_mat[element.first];
                cout << element.first << ":(" << u << ',' << d << ',' << l << ',' << r << ")\n";
            }

            for(const auto & element: graph) {
                cout << element.first << " -> (";
                for(const auto & adj: element.second) {
                    cout << adj << ',';
                }
                cout << '\n';
            }

            for(const auto & element: inDegree) {
                cout << element.first << ": " << element.second << '\n';
            }

            cout << count << ' ' << n << '\n';
            #endif

            return count == n;
        }
    };

class Solution {
public:
    int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
        // 2 times bfs. First get all the boxes final status. Second get the candies.
        queue<int> q;
        for(const auto & init: initialBoxes) {
            q.emplace(init);
        }
        while(!q.empty()) {
            int cur = q.front();
            q.pop();
            if(status[cur] == 1) {
                for(const auto & key: keys[cur]) {
                    status[key] = 1;
                }
            }
            for(const auto & adj: containedBoxes[cur]) {
                q.emplace(adj);
            }
        }
        // Then get the boxes candies.
        int ans = 0;
        for(const auto & init: initialBoxes) {
            q.emplace(init);
        }
        while(!q.empty()) {
            int cur = q.front();
            q.pop();
            if(status[cur] == 1) {
                ans += candies[cur];
            }
            for(const auto & adj: containedBoxes[cur]) {
                q.emplace(adj);
            }
        }
        return ans;
    }
};

事务基础与并发控制

事务

• 事务 (Transaction) 是什么？
  • 是一组数据库运算的集合，可以抽象成一个的不可分的逻辑工作单元

ACID 特性

• 事务具有 ACID 特性
  • Atomicity: 原子性，即不可分割。事务要么完全执行，要么完全不执行。
  • Consistency: 事务必须保持数据库系统满足持续性，也就是满足数据库系统中的原先拥有的关系和条件。
  • Isolation: 隔离性，每个事务都是独立运行，相当于仅仅在单独运行自己。
  • Durability: 持续性。事务必须可以从错误中恢复。

并发控制

• 什么是并发控制？并发控制的目的是什么？
  • 并发控制是数据库系统保证多个事务运算正确交叠的机制。目的是为了保证事务之间的隔离性，同时增加数据库处理速度，提高吞吐率。

保证正确的交叠：从序列化执行开始

为了简化调度方式，将数据库内的所有操作都看做仅有对特定资源的读取和写入操作。我们用 $R_i(A)$ 表示第 i 个事务读取数据 A，$W_i(A)$ 表示第 i 个事务写入数据 A。

序列化调度与等价调度

• 没有任何交叠操作的调度 -> 序列化调度。即完成一个事务的所有操作才去执行下一个事务的操作。
• 等价调度是一组执行效果相同的调度的集合。

可以序列化的调度

• 具有交叠操作的调度等价于某些事务的序列化操作。
• 每个可序列化的调度都可以确保持续性的时候，我们的序列化调度是可持续的。
• 需要我们判断调度是否可序列化。

判断调度可序列化

矛盾操作

• 一对矛盾的操作将具有：
  • 不同的事务面向同一份资源。
  • 至少有一个操作是写操作。
• 这样我们有：(R1W2 不可重复读),(W1R2 脏页读),(W1W2 更新丢失) 均为矛盾操作。（目前不考虑假性读取和写入偏移）

可序列化的不同层级

• 冲突可序列 (confilict serializability)

  • 两个调度是冲突等价的，当且仅当
    • 拥有相同事务且事物内部操作相同。
    • 两个调度中冲突操作的顺序是相同的。也就是说如果调度一中是 (R1W2),那么调度二也必须保证 R1 在 W2 之前。
  • 调度 $S$ 是冲突可序列的，当它
    • 在冲突操作上的顺序与某些序列化调度相同。也就是说，你可以将他转换成序列化调度。

• 视图可序列 (view serializability)

  • 两个调度是视图等价的当它们
    • 事务 1 在调度 1 中读取的初始值和在调度 2 中读取的初始值相同。
    • 事务 1 在调度 1 中读取到事务 i 写入的值，则在调度 2 中也应该读取到事务 i 写入的值。
    • 所有的最终结果都必须由一个事务来完成。

• 很显然冲突可序列化是比视图可序列化更严格 的。

前序图

• 判断是否冲突可序列化的简单的方法。
• 每个事务作为一个节点。每个冲突操作对作为一条边。
• 当前序图是有向无环图时，恭喜你它是冲突可序列化的。

并发控制方法

为了保证得到正确的交叠操作调度，我们需要一些并发控制方法。

锁的类型（其实是读写锁换皮）

• 共享锁：用于读操作的共享锁。
• 排它锁：用于写操作的排它锁。

简单的排它锁和共享锁无法保证可序列性。

二阶段锁

• 阶段一：获得锁

  • 每个事务获取他所需要的锁。
  • 可能被拒绝或允许，但是在该阶段不允许有释放锁的行为。

• 阶段二：释放锁

  • 每个事务释放它所需要的锁。
  • 不允许任何事务获得锁。
  • 严格的二阶段锁：在所有事务结束后才能统一释放锁。可以解决脏页读问题。
  • 二阶段锁可能导致死锁。通过检测和预防来避免死锁 (银行家算法等...)
  • 这里不探索如何解决死锁。

• 一个调度是严格的当一个事务写入一份数据后，其他事务不能读取或覆盖这份数据，直到该事务终结。

• 可以看出严格程度：严格序列化 > 严格二阶段锁 > 冲突可序列化 > 视图可序列化

时间戳排序控制 (T/O)

• 采用时间戳来决定序列化调度中事务执行的顺序。当 TS(T1)<TS(T2) 的时候，执行顺序必须为 T1 -> T2.
• 基础时间戳
  • 事务自身将拥有时间戳；TS( $T_i$ )
  • 每个数据对象也将有自己的时间戳。
    • 数据 X 的读时间戳：R(X)
    • 数据 X 的写时间戳：W(X)

基础时间戳控制

• 读操作

  • 当 TS(T) < W(X) 的时候，回滚并重新开始，赋予新的 TS(T).
  • 否则持续执行并且 $R(X)=\max(R(X),TS(T))$.
  • 允许拷贝一份 X 来保证重复读取。

• 写操作

  • 当 TS(T) < W(X) 或者 TS(T) < R(X) 的时候，回滚并重新开始，赋予新的 TS(T).
  • 否则持续执行并且 $W(X)=\max(W(X),TS(T))$

• 基础的时间戳操作保证了冲突可序列性质。

托马斯写 + 时间戳控制

• 写操作处有所不同。

  • 当 TS(T) < R(X) 的时候，回滚。
  • 当 TS(T) < W(X) 的时候，忽略写操作，继续执行（因为很快时间戳后面的事务的写操作将覆盖本次的写操作）。
  • 否则持续执行并且 $W(X)=\max(W(X),TS(T))$

• 很明显仅保证视图可序列性。

OCC(乐观并发控制)

• 时间戳协议。
• DBMS 为每一个事务创建了一个私有的工作空间。
  • 每个被读取的对象将被复制到工作空间中，对对象的编辑也将加入到工作空间中。
  • 当事务提交时，DBMS 将会对比工作空间写集合，每个事务的写空间相同时，装载到全局数据库中。

三阶段

• Read，读取。跟踪每个事务的读、写集合，储存他们的写入对象到私有的工作空间中。DBMS 将会复制一个事务中所有需要的元组到共享数据库中保证可重复读。
• Validation，验证。给每一个事务独有的时间戳，检查他们是否于其他对象相互冲突。
  • 当事务唤起提交时，进入验证部分。
  • 前向验证：检查正在提交中的事务读/写集合是否与活动中的未提交事务相互重叠。
    • 检查时间戳。当提交事务时间戳小于其他活动事务时，需要满足三个条件：
      • (1) 其他事务读阶段位于当前事务写阶段完成之后。R2(A)>W1(A)
      • (2) 其他事务写阶段在当前事务写阶段完成之后。W2(A)>W1(A)， 并且 当前事务没有修改任何其他活动事务要读取的对象。
      • (3) 其他事务读阶段在当前事务读阶段完成之后。R2(A)>R1(A), 并且当前事务不修改任何T2 将会读取或写入的对象。
    • 反向验证：检查正在提交中的事务读/写集合是否与活动中的已提交事务相互重叠。仍然遵循三条原则。
• Write，写。当验证成功时，对所有已经编辑过的对象设置写时间戳，装载他们进入全局数据空间。否则回滚，中断事务。

class Solution {
public:
    string lastSubstring(string s) {
        int i = 0, j = 1, n = s.size();
        while (j < n) {
            int k = 0;
            while (j + k < n && s[i + k] == s[j + k]) {
                k++;
            }
            if (j + k < n && s[i + k] < s[j + k]) {
                int t = i;
                i = j;
                j = max(j + 1, t + k + 1);
            } else {
                j = j + k + 1;
            }
        }
        return s.substr(i, n - i);
    }
    string answerString(string word, int numFriends) {
        if(numFriends == 1) {
            return word;
        }
        string last = lastSubstring(word);
        int n = word.size(), m = last.size();
        return last.substr(0, min(m, n - numFriends + 1));
    }
};

#define DEBUG
#undef DEBUG
class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, unordered_set<char>> graph;
        unordered_map<char, int> inDegree;
        bool flag = false;
        auto add_edge = [&](const string & l, const string & r) -> void {
            int i = 0;
            for(i = 0; i < min(l.length(), r.length()); i++) {
                if(graph.find(l[i]) == graph.end()) {
                    graph[l[i]] = unordered_set<char>();
                }
                if(inDegree.find(l[i]) == inDegree.end()) {
                    inDegree[l[i]] = 0;
                }
                if(l[i] != r[i] && graph[l[i]].find(r[i]) == graph[l[i]].end()) {
                    flag = true;
                    graph[l[i]].insert(r[i]);
                    inDegree[r[i]]++;
                    break;
                }
                else if(l[i] != r[i]) {
                    flag = true;
                    break;
                }
            }
            if(!flag && l.length() > r.length()) {
                return;
            }
            flag = true;
            int temp = i;
            for(; i < l.length(); i++) {
                if(graph.find(l[i]) == graph.end()) {
                    graph[l[i]] = unordered_set<char>();
                }
                if(inDegree.find(l[i]) == inDegree.end()) {
                    inDegree[l[i]] = 0;
                }
            }
            i = temp;
            for(; i < r.length(); i++) {
                if(graph.find(r[i]) == graph.end()) {
                    graph[r[i]] = unordered_set<char>();
                }
                if(inDegree.find(r[i]) == inDegree.end()) {
                    inDegree[r[i]] = 0;
                }
            }
        };

        // Step 1: Add edges.
        if(words.size() == 1) {
            flag = true;
            for(int i = 0; i < words[0].length(); i++) {
                if(graph.find(words[0][i]) == graph.end()) {
                    graph[words[0][i]] = unordered_set<char>();
                }
                if(inDegree.find(words[0][i]) == inDegree.end()) {
                    inDegree[words[0][i]] = 0;
                }
            }
        }
        else {
            for(int i = 0; i < words.size(); i++) {
                for(int j = i + 1; j < words.size(); j++) {
                    add_edge(words[i], words[j]);
                }
            }
        }

        #ifdef DEBUG
        for(auto & elem: graph) {
            cout << elem.first << ": ";
            for(const auto & adj: elem.second) {
                cout << adj << ' ';
            }
            cout << '\n';
        }
        for(auto & elem: inDegree) {
            cout << elem.first << ": " << elem.second << "\n";
        }
        string flag_str = (flag == true) ? "true" : "false";
        cout << flag_str << '\n';
        #endif

        // Step 2: TopoSort.
        queue<char> q;
        string ans;
        for(const auto & ch: inDegree) {
            if(ch.second == 0) {
                q.emplace(ch.first);
            }
        }
        while(!q.empty()) {
            char ch = q.front();
            ans.push_back(ch);
            q.pop();
            for(const auto & adj: graph[ch]) {
                if(--inDegree[adj] == 0) {
                    q.emplace(adj);
                }
            }
        }
        return ans.length() == graph.size() && flag ? ans : "";
    }
};

基于基环树的思想。

class Solution {
public:
    int maximumInvitations(vector<int>& favorite) {
        int n = favorite.size();
        vector<vector<int>> reverse_graph(n);
        queue<int> q;
        vector<int> inDegree(n, 0);

        for(int i = 0; i < n; i++) {
            inDegree[favorite[i]]++;
        }
        for(int i = 0; i < n; i++) {
            if(inDegree[i] == 0) {
                q.emplace(i);
            }
        }

        while(!q.empty()) {
            int cur = q.front();
            q.pop();
            // Build reverse_graph;
            reverse_graph[favorite[cur]].emplace_back(cur);
            if(--inDegree[favorite[cur]] == 0) {
                q.emplace(favorite[cur]);
            }
        }
        
        // Dfs reverse graph find the shortest edge.
        auto dfs = [&](this auto && dfs, int from) -> int {
            int max_depth = 1;
            for(const auto & adj: reverse_graph[from]) {
                max_depth = max(max_depth, dfs(adj) + 1);
            }
            return max_depth;
        };

        // Find the cycle.
        int ring = 0, chain = 0;
        for(int i = 0; i < n; i++) {
            if(inDegree[i] == 0) {
                continue;
            }
            inDegree[i] = 0;
            int tmp_ring = 1;
            for(int adj = favorite[i]; adj != i; adj = favorite[adj]) {
                inDegree[adj] = 0;     // mark as visited.
                tmp_ring++;
            }
            
            if(tmp_ring == 2) {
                chain = chain + dfs(i) + dfs(favorite[i]);
            } else {
                ring = max(ring, tmp_ring);
            }
        }
        return max(chain, ring);
    }
};

// #define debug
class Union {
        public:
        vector<int> parent;
        int n;
        // The Costruction function.
        Union(int n):n(n),parent(vector<int>(n)) {
            iota(parent.begin(), parent.end(), 0);
        }
    
        // Path compression. Find parent until the same.
        int find(int id) {
            if(parent[id] != id) {
                parent[id] = find(parent[id]);
            }
            return parent[id];
        }
    
        // Merge by size. You can also make it by rank, for modified as size[pa_i] += 1;
        void merge(int id1, char id2) {
            // Find parent.
            int pa1 = find(id1);
            int pa2 = find(id2);
    
            if(pa1 == pa2) {
                return;
            }
            else if(pa1 < pa2) {
                parent[pa2] = pa1;
            }
            else {
                parent[pa1] = pa2;
            }
        }
    
        bool judge(int id1, int id2) {
            return find(id1) != find(id2);
        }
    };
class Solution {
public:
    string smallestEquivalentString(string s1, string s2, string baseStr) {
        Union u(26);
        for(int i = 0; i < s1.length(); i++) {
            u.merge(s1[i] - 'a', s2[i] - 'a');
        }
        #ifdef debug
        for(auto & element: u.parent) {
            cout << element.first << ' ' << element.second << '\n';
        }
        #endif
        string ans;
        for(int i = 0; i < baseStr.length(); i++) {
            ans.push_back(u.find(baseStr[i] - 'a') + 'a');
        }
        return ans;
    }
};

class Solution {
public:
    string robotWithString(string s) {
        int n = s.length();
        vector<char> min_str(n+1);
        min_str[n] = 'z';
        for(int i = n - 1; i >= 0; i--) {
            min_str[i] = min(min_str[i+1], s[i]);
        }
        stack<char> st;
        string ans;
        for(int i = 0; i < n; i++) {
            st.push(s[i]);
            while(!st.empty() && st.top() <= min_str[i+1]) {
                ans.push_back(st.top());
                st.pop();
            }
        }
        return ans;
    }
};

template<typename T>
class DataStructure {
        public:
        // Data Definition start
        // ********
        // Data Definition end
        std::shared_mutex rwlock;
        
        template<typename T>
        T read() {
                std::shared_lock rlock(rwlock);  // Read operations with shared_lock;
                // Read Operations;
        }
        template<typename T>
        void write() {
                std::unique_lock wlock(rwlock);  // Write operations with exclusive_lock.
                // Write operations;
        }
};

#include<ranges>
class Solution {
    public:
        string clearStars(string s) {
            vector<stack<int>> indices(26, stack<int>());
            int count = 0;
            for(int i = 0; i < s.length(); i++) {
                if(s[i] == '*') {
                    for(int i = 0; i < 26; i++) {
                        if(!indices[i].empty()) {
                            s[indices[i].top()] = '*';
                            indices[i].pop();
                            break;
                        }
                    }
                } else indices[s[i] - 'a'].push(i);
            }
            return s | ranges::views::filter([](char i) {return i != '*';}) 
                    | ranges::to<std::string>();
        }
    };

class Solution {
public:
    int longestCycle(vector<int>& edges) {
        // TopoSort to modify the graph.
        int n = edges.size();
        vector<int> inDegree(n, 0);
        for(int i = 0; i < n; i++) {
            if(edges[i] != -1) inDegree[edges[i]]++;
        }
        queue<int> q;
        for(int i = 0; i < n; i++) {
            if(inDegree[i] == 0) {
                q.emplace(i);
            }
        }
        while(!q.empty()) {
            int cur = q.front();
            q.pop();
            int adj = edges[cur];
            edges[cur] = -1;
            if(adj != -1 && --inDegree[adj] == 0) {
                q.emplace(adj);
            }
        }
        int ans = -1;
        auto dfs = [&](this auto && dfs, int from) -> int {
            int nxt = edges[from];
            if(nxt == -1) return 0;
            edges[from] = -1;
            return dfs(nxt) + 1;
        };
        for(int i = 0; i < n; i++) {
            ans = max(ans, dfs(i));
        }
        return ans == 0 ? -1 : ans;
    }
};

class Solution {
public:
    int findShortestCycle(int n, vector<vector<int>>& edges) {
        // Build graph.
        vector<vector<int>> graph(n);
        for(const auto & edge: edges) {
            int u = edge[0], v = edge[1];
            graph[u].emplace_back(v);
            graph[v].emplace_back(u);
        }
        int * distance = new int [n];
        // Dijkstra with delete the edge. For indirect graph, pick one side, run dijkstra.
        // Directed should strictly follow start and end point.
        auto bfs = [&](int u, int v) -> void {
            queue<int> q;
            q.emplace(u);
            distance[u] = 0;
            while(!q.empty()) {
                int cur = q.front();
                q.pop();
                for(const auto & adj: graph[cur]) {
                    // False delete.
                    if(cur == u && adj == v) {
                        continue;
                    }
                    // Updated.
                    else if(distance[adj] < 0x7f7f7f7f) {
                        continue;
                    }
                    else if(distance[adj] > distance[cur] + 1) {
                        distance[adj] = distance[cur] + 1;
                        q.emplace(adj);
                    }
                }
            }
        };
        int ans = INT_MAX / 2;
        for(const auto & edge: edges) {
            memset(distance, 0x7f, sizeof(int) * n);
            int u = edge[0], v = edge[1];
            bfs(u, v);
            ans = min(ans, distance[v] + 1);
        }
        return ans == INT_MAX / 2 ? -1 : ans;
    }
};