第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號安全,請及時綁定郵箱和手機立即綁定

力扣2858題:從BFS到動態(tài)規(guī)劃巧解有向圖

標簽:
C++

https://img1.sycdn.imooc.com/6ca08868089ee37d17300804.jpg

一、问题理解

给定一个有向图,如果将所有边视为无向边,则形成一棵树。我们需要为每个节点计算,以该节点为根时,最少需要反转多少条边的方向,才能从该节点到达所有其他节点。

二、解题思路

  1. 树的性质‌:由于无向图是一棵树,所以任意两点之间有且只有一条路径。

  2. 关键观察‌:从根节点到子节点的边方向决定了是否需要反转。

  3. 递推关系‌:相邻节点的反转次数可以通过父节点的反转次数推导出来。

三、算法详解

  1. 构建邻接表‌:

  • 存储每个节点的邻居,并标记边的方向(原始方向或反向)

第一次BFS‌:

  • 以节点0为根,计算从0出发到达所有节点需要的反转次数

  • 遇到反向边时增加反转计数

第二次BFS‌:

  • 利用递推关系计算其他节点为根时的反转次数

  • 对于边u->v(原始方向),res[v] = res[u] + 1

  • 对于边v->u(反向边),res[v] = res[u] - 1

返回结果‌:

  • 存储每个节点作为根时的最少反转次数

四、完整代码

class Solution {public:
    vector<int> minEdgeReversals(int n, vector<vector<int>>& edges) {
        // 构建邻接表,同时记录边的方向
        vector<vector<pair<int, bool>>> adj(n);
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            adj[u].emplace_back(v, true);  // 原始方向
            adj[v].emplace_back(u, false); // 反向边
        }

        // 第一次BFS,计算以0为根时的反转次数
        vector<int> res(n, 0);
        queue<int> q;
        vector<bool> visited(n, false);
        q.push(0);
        visited[0] = true;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto& [v, dir] : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    if (!dir) { // 如果是反向边,需要反转
                        res[0]++;
                    }
                    q.push(v);
                }
            }
        }

        // 第二次BFS,计算其他节点为根时的反转次数
        q.push(0);
        fill(visited.begin(), visited.end(), false);
        visited[0] = true;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto& [v, dir] : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    // 关键递推公式
                    res[v] = res[u] + (dir ? 1 : -1);
                    q.push(v);
                }
            }
        }

        return res;
    }};

五、示例分析

以n=3,edges=[[1,0],[2,1]]为例:

  1. 以0为根:需要反转2条边(0->1和1->2)

  2. 以1为根:需要反转1条边(1->2)

  3. 以2为根:需要反转0条边

来源:力扣2858题:从BFS到动态规划巧解有向图


點擊查看更多內(nèi)容
TA 點贊

若覺得本文不錯,就分享一下吧!

評論

作者其他優(yōu)質(zhì)文章

正在加載中
  • 推薦
  • 評論
  • 收藏
  • 共同學習,寫下你的評論
感謝您的支持,我會繼續(xù)努力的~
掃碼打賞,你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃,即可進行掃碼打賞哦
今天注冊有機會得

100積分直接送

付費專欄免費學

大額優(yōu)惠券免費領(lǐng)

立即參與 放棄機會
微信客服

購課補貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動學習伙伴

公眾號

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號

舉報

0/150
提交
取消