6134. 找到离给定两个节点最近的节点-力扣双百代码

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

给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点 至多 有一条出边。

有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边，那么 edges[i] == -1 。

同时给你两个节点 node1 和 node2 。

请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案，请返回 最小 的节点编号。如果答案不存在，返回 -1 。

注意 edges 可能包含环。

示例 1：

输入：edges = [2,2,3,-1], node1 = 0, node2 = 1
输出：2
解释：从节点 0 到节点 2 的距离为 1 ，从节点 1 到节点 2 的距离为 1 。
两个距离的较大值为 1 。我们无法得到一个比 1 更小的较大值，所以我们返回节点 2 。

示例 2：

输入：edges = [1,2,-1], node1 = 0, node2 = 2
输出：2
解释：节点 0 到节点 2 的距离为 2 ，节点 2 到它自己的距离为 0 。
两个距离的较大值为 2 。我们无法得到一个比 2 更小的较大值，所以我们返回节点 2 。

解题代码如下：

void dfs( int* edges, int edgesSize, int node,int *dnode,int d,int *r){
     r[node]++;
     if(d<dnode[node]&&r[node]<=1){
        
         dnode[node]=d;
     }
     if(edges[node]!=-1&&r[node]<2){
         dfs(edges,edgesSize,edges[node],dnode,d+1,r);

     }

}
void dfs2( int* edges, int edgesSize, int node,int *dnode,int d,int *r){
     r[node]++;
  //   printf("ndoe  %d ",node);
     if(d>dnode[node]&&r[node]<=1){
        
         dnode[node]=d;
     }
     // printf("edges[node] r[node] %d %d ",edges[node],r[node]);
     if(edges[node]!=-1&&r[node]<2){
  //   printf("dfasfsd");
         dfs2(edges,edgesSize,edges[node],dnode,d+1,r);
     //   printf(" sdfasfsd");
     }

}


int closestMeetingNode(int* edges, int edgesSize, int node1, int node2){
    int *dnode=(int *)malloc(sizeof(int )*edgesSize);
    int *r=(int *)malloc(sizeof(int )*edgesSize);
    int *r2=(int *)malloc(sizeof(int )*edgesSize);
    int i;
    for(i=0;i<edgesSize;i++){
        dnode[i]=1000000;
        r[i]=0;
         r2[i]=0;
    }
     dfs(edges,edgesSize,node1,dnode,0,r);
    
      dfs2(edges,edgesSize,node2,dnode,0,r2);
      int min=10000000;
     
    
    
      for(i=0;i<edgesSize;i++){
          if(dnode[i]<min&&r[i]>=1&&r2[i]>=1){
               min=dnode[i];
          }
      }
      //printf("min %d ",min);
        for(i=0;i<edgesSize;i++){
          
            if(dnode[i]==min&&r[i]>=1&&r2[i]>=1){
                return i;
            }
        }
      return -1;



}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64