leetcode-6134: Find the closest node to the given two nodes

题目

题目连接
给你一个 n 个节点的 有向图 ,节点编号为 0 到 n - 1 ,每个节点 至多 有一条出边.

Directed graphs use a size of n 下标从 0 开始的数组 edges 表示,表示节点 i There is a directed edge pointing edges[i] .如果节点 i 没有出边,那么 edges[i] == -1 .

Gives you two nodes at the same time node1 和 node2 .

Please return a slave node1 和 node2 can reach the node number,使节点 node1 和节点 node2 distance to this node Larger values ​​are minimized.如果有多个答案,请返回 最小 的节点编号.如果答案不存在,返回 -1 .

注意 edges May contain rings.

示例 1：

输入：edges = [2,2,3,-1], node1 = 0, node2 = 1
输出：2
解释：从节点 0 到节点 2 的距离为 1 ,从节点 1 到节点 2 的距离为 1 .
The larger of the two distances is  1 .We can't get a ratio 1 smaller larger value,So we return to node 2 .

示例 2：

输入：edges = [1,2,-1], node1 = 0, node2 = 2
输出：2
解释：节点 0 到节点 2 的距离为 2 ,节点 2 The distance to itself is  0 .
The larger of the two distances is  2 .We can't get a ratio 2 smaller larger value,So we return to node 2 .

解题

方法一：哈希

创建1a set of hashes,记录从node1Node to start traversing,那么从node2开始遍历,第一次经过setNodes that already exist in ,Then it's the intersection.
But at this time there is no guarantee that it is the minimum distance,So repeat the same thing again,从node2The starting node is recorded toset,然后从node1Begin to meet for the first timesetexisting nodes in .
Take the minimum of the two path results,is the final node.

创建2个数组,visitThe array records whether the node has been visited,lenThe array records the distance from the current node to the starting node
从node1开始,traverse to the end（-1, or a point that has already been visited）,同时更新visit和len数组

class Solution {
    
public:
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
    
        pair<int,int> p1=fun(edges,node1,node2);
        pair<int,int> p2=fun(edges,node2,node1);
        if(p1.first==p2.first) return p1.first;//如果是同一个节点,Then return directly to the node
        else{
    
            if(p1.second==p2.second) return min(p1.first,p2.first);//如果节点不同,But the distance is the same,Select the node with the lower number
            else if(p1.second<p2.second) return p1.first;//如果节点不同,and different distances,Then select the node with the smallest distance
            else return p2.first;
        }
        
        
    }
    pair<int,int> fun(vector<int>& edges, int node1, int node2){
    //返回值：（节点,路径）
        unordered_set<int> set;//记录node1开始,经过的节点
        vector<bool> visit(edges.size(),false);//visitThe array records whether the node has been visited（作用：防止出现环,死循环）

        int i=node1;
        vector<int> len(edges.size(),-1);//lenThe array records the distances of the nodes passednode1的距离
        int curLen=0;
        while(true){
    
            if(i==-1||visit[i]==true) break;//If the node has no outgoing edges 或者 节点访问过,那么直接break
            visit[i]=true;
            len[i]=curLen++;
            set.insert(i);
            i=edges[i];//访问下一个节点
        }

        visit=vector<bool>(edges.size(),false);
        i=node2;
        curLen=0;
        while(true){
    
            if(i==-1||visit[i]==true) return {
    -1,-1};
            visit[i]=true;
            if(set.count(i)){
    //If the node is fromnode1started visiting,Explain that this is an intersection
                int resLen=max(len[i],curLen);//Take the largest path
                return {
    i,resLen};
            }
            curLen++;
            i=edges[i];
        }
        return {
    -1,-1};
    }
};