锻炼身体

思路

牛牛希望走的距离尽可能短,牛妹希望牛牛走的距离尽可能长,因此,牛妹会放到一个点 , 该点要满足与牛妹起点 的距离小于该点与牛牛起点的距离,通过 dfs 分别求出 号点和 号点到其他点的距离,对满足条件的点中,取一个与 号点距离的最大值即可。
时间复杂度:

/**
 * struct Point {
 *    int x;
 *    int y;
 * };
 */

class Solution {
private:
    #define maxn 100010
    vector<int> g[maxn];
    int dis[2][maxn];
public:

    void dfs(int x, int fa, int id) {
        dis[id][x] = dis[id][fa] + 1;
        for (auto v: g[x]) {
            if (v == fa) continue;
            dfs(v, x, id);
        }
    }
    int solve(int n, int x, vector<Point>& Edge) {

        // write code here
        for (int i = 1; i <= n; ++i) {
            g[i].clear();
            dis[0][i] = dis[1][i] = 0;
        }
        for (auto cur: Edge) {
            g[cur.x].push_back(cur.y);
            g[cur.y].push_back(cur.x);
        }
        dfs(1, 0, 0);
        dfs(x, 0, 1);

        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            if (dis[0][i] > dis[1][i])
                ans = max(ans, dis[0][i]);
        }
        return ans;
    }
};
全部评论

相关推荐

双非Java现在无实习,应该好好背八股,找个开源项目做做,还是应该疯狂投实习呢?
Aries_woon:投实习并不耽误你做开源项目,集中一个下午可以投几十家实习了,投完安心做项目等待面试通知
点赞 评论 收藏
分享
暴走萝莉莉:这是社招场吧,作为HR说个实话:这个维护关系的意思是要有政府资源,在曾经的工作中通过人脉资源拿下过大订单的意思。这个有相关管理经验,意思也是真的要有同岗位经验。应酬什么的对于业务成交来说就算不乐意也是常态,就是要求说话好听情商高,酒量好。
点赞 评论 收藏
分享
寿命齿轮:实习就一段还拉了,项目一看就不是手搓,学历也拉了,技术栈看着倒是挺好,就是不知道面试表现能咋样。 不过现在才大三,争取搞两端大厂实习,或者一个纯个人项目+一段大厂,感觉秋招还是未来可期。
投递美团等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务