【Leetcode】2359. Find Closest Node to Given Two Nodes

题目地址：

https://leetcode.com/problems/find-closest-node-to-given-two-nodes/description/

给定一个$n$阶无权有向图，顶点编号$0\sim n-1$，图以向量$v$给出，$v[u]=-1$指的是$u$没有出边；否则指$u$指向$v[u]$。给定两个顶点$u,v$，要求求一个点$x$，使得 max ⁡ { d ( u , x ) , d ( v , x ) } \max\{d(u,x),d(v, x)\} max{d(u,x),d(v,x)}最小。如果不存在$u,v$都能到达的点，则返回$-1$。

可以两遍BFS，分别求一下$u$和$v$所能到达的顶点和距离，然后枚举一下哪个顶点满足要求。代码如下：

class Solution {public:int closestMeetingNode(vector<int>& g, int node1, int node2) {int n = g.size();vector<int> dist1(n, -1), dist2(n, -1);bfs(node1, g, dist1);bfs(node2, g, dist2);int mind = INT_MAX, res = -1;for (int i = 0; i < n; i++) {int d = -1;if (~dist1[i] && ~dist2[i]) d = max(d, max(dist1[i], dist2[i]));if (~d && d < mind) {mind = min(mind, d);res = i;}}return res;}void bfs(int u, vector<int>& g, vector<int>& dist) {queue<int> q;q.push(u);dist[u] = 0;while (q.size()) {int t = q.front();q.pop();int ne = g[t];if (~ne && dist[ne] == -1) {dist[ne] = dist[t] + 1;q.push(ne);}}}
};

时空复杂度$O(n)$。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！