[LeetCode304 Weekly Competition] Two questions about the base ring tree 6134. Find the closest node to the given two nodes, 6135. The longest cycle in the graph

LeetCode304周赛

https://leetcode.cn/contest/weekly-contest-304/
Record two unwritten questions
Reference explanation：Y总
这是一个基环树问题,Just a bunch of trees hanging from a ring.

LeetCode 6134. 找到离给定两个节点最近的节点

https://leetcode.cn/problems/find-closest-node-to-given-two-nodes/
解决思路：分别从 node1 和 node2 开始,Record each node to node1 和 node2 的距离,If there is a loop or it ends at the end.然后遍历节点,If you want the smallest max(d1[i], d2[i]) 的节点 i.

class Solution {
    
public:
    int closestMeetingNode(vector<int>& p, int x, int y) {
    
        int n = p.size(); // 记录点数
        vector<int> d1(n, -1); // Record every arrival x 的距离
        vector<int> d2(n, -1); // Record every arrival y 的距离
        d1[x] = d2[y] = 0;
        while (p[x] != -1) {
    
            if (d1[p[x]] != -1) {
     // 已经遍历过,跳出循环
                break;
            }
            d1[p[x]] = d1[x] + 1; // 节点距离 + 1
            x = p[x];
        }

        while (p[y] != -1) {
    
            if (d2[p[y]] != -1) {
     // 已经遍历过,跳出循环
                break;
            }
            d2[p[y]] = d2[y] + 1; // 节点距离 + 1
            y = p[y];
        }

        int ans = -1, id = -1;

        for (int i = 0; i < n; i++) {
    
            int a = d1[i], b = d2[i];
            if (a != -1 && b != -1) {
    
                if (ans == -1 || max(a, b) < ans) {
     // If a node distance x 和 y 更近,记录为 ans
                    ans = max(a, b);
                    id = i;
                }
            }
        }

        return id;
    }
};

LeetCode 6135. 图中的最长环

https://leetcode.cn/problems/longest-cycle-in-a-graph/
解决思路：Number of loop nodes n 次,每次从第 i 个节点开始,If there is a loop or it ends at the end,Record the length you can walk.最终结果就是取 n The longest route length that a node can travel from the beginning.

class Solution {
    
    
public:
    vector<int> p;
    vector<bool> st; // Stores whether each point has been searched
    vector<int> in_stk; // is on the stack,深度为多少
    int ans = -1;
    
    void dfs(int x, int depth){
    
        st[x] = true; // 表示被遍历过
        in_stk[x] = depth; // 加入栈,Marked as the depth of the stack

        int next = p[x];    // 搜索 x 的下一个节点
        if (next != -1) {
    
            if (!st[next]) {
     // not searched
                dfs(j, depth + 1);
            } else if (in_stk[next]) {
     //被搜索过,在栈中,有环
                ans = max(ans, depth + 1 - in_stk[next]);    // 深度更新
            }
        }

        in_stk[x] = 0; // 出栈,标记清空
    }

    int longestCycle(vector<int>& p) {
    
        this->p = p;
        int n = p.size(); // 节点个数

        st = vector<bool>(n);
        in_stk = vector<int>(n);
        
        for (int i = 0; i < n; i++) {
     // 遍历所有点
            if (!st[i]) {
     // If the current point has not been searched
                dfs(i, 1);
            }
        }

        return ans;
    }
};