leetcode与数据结构---310,802

程序员文章站 2022-07-13 21:09:43

...

leetcode与数据结构—310,802

题目描述

题802

在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。

现在, 如果我们最后能走到终点，那么我们的起始节点是最终安全的。更具体地说, 存在一个自然数 K, 无论选择从哪里开始行走, 我们走了不到 K 步后必能停止在一个终点。

哪些节点最终是安全的？结果返回一个有序的数组。

该有向图有 N 个节点，标签为 0, 1, ..., N-1, 其中 N 是 graph 的节点数. 图以以下的形式给出: graph[i] 是节点 j 的一个列表，满足 (i, j) 是图的一条有向边。

示例：
输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出：[2,4,5,6]
这里是上图的示意图。

leetcode与数据结构---310,802

题310

对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。

格式

该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。

你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。

示例 1:

输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3 

输出: [1]

示例 2:

输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

输出: [3, 4]

说明:

根据树的定义，树是一个无向图，其中任何两个顶点只通过一条路径连接。换句话说，一个任何没有简单环路的连通图都是一棵树。
树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

题目解答

这两题有一定的相似之处，题目310的解题思路算比较巧妙的，利用剪枝的思想。首先要明白最小高度树的根绝对不对在叶节点上，那么我们的做法就是，每次将该树所有叶节点(即度为一的节点)删去，然后判断最后剩余的几点个数是否小于二，如果不是继续剪枝，那么最后剩余的一个或者两个节点即为所需要求的根节点，一个具体例子如下：

leetcode与数据结构---310,802

具体代码如下：

class Solution {
public:
    map<int, vector<int>> NodeInfo;
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        int *ALLlength = new int[n];
        vector<int> result;
        map<int, bool> flag;
        //first, we use map to store node's neighbor        
        for (size_t i = 0; i < edges.size(); i++) {
            NodeInfo[edges[i].first].push_back(edges[i].second);
            NodeInfo[edges[i].second].push_back(edges[i].first);
        }
        map<int, vector<int>>::iterator iter;
        queue<int> Node4Delete;
        while (NodeInfo.size() > 2) {   
            for (int i = 0; i < n; i++)
                flag[i] = false;

            for (iter = NodeInfo.begin(); iter != NodeInfo.end();) {
                if ((*iter).second.size() == 1 && flag[(*iter).first] == false) {       
                    int leaf = (*iter).first;                   
                    int neighbor = (*iter).second[0];
                    flag[neighbor] = true;
                    iter = NodeInfo.erase(iter);
                    vector<int>::iterator iter_vec;
                    for (iter_vec = NodeInfo[neighbor].begin(); iter_vec != NodeInfo[neighbor].end();)
                        if (*(iter_vec) == leaf)
                            iter_vec = NodeInfo[neighbor].erase(iter_vec);
                        else
                            iter_vec++;
                }
                else
                    iter++;
            }
        }
        iter = NodeInfo.begin();
        result.push_back((*iter).first);
        if (NodeInfo.size() == 2)
            result.push_back((*(++iter)).first);
        return result;
    }
};

而对于题目802，与302有些许类似之处。题目802需要返回哪些一定能够走到终点即出度为0的节点，那么我们也可以用剪枝的思想。即每次将出度为0的节点入队列然后一一删去出队列，再判断整个图是否仍然有出度为0的节点，直到队列为空。具体实例如下：

leetcode与数据结构---310,802

具体代码如下：

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        queue<int> q;
        map<int, vector<int>> NodeIn;
        map<int, int> NodeOut;
        vector<int> result;
        int num = graph.size();
        for (size_t i = 0; i < num; i++) {
            NodeOut[i] += graph[i].size();
            for (size_t j = 0; j < graph[i].size(); j++) {
                NodeIn[graph[i][j]].push_back(i);               
            }
        }

        for (int i = 0; i < num; i++) {
            if (NodeOut[i] == 0) {
                q.push(i);
                result.push_back(i);
            }
        }

        while (!q.empty()) {
            for (size_t i = 0; i < NodeIn[q.front()].size(); i++) {
                int its_proceed = NodeIn[q.front()][i];
                NodeOut[its_proceed]--;
                if (NodeOut[its_proceed] == 0) {
                    q.push(its_proceed);
                    result.push_back(its_proceed);
                }
            }
            q.pop();
        }

        sort(result.begin(), result.end());
        return result;
    }
};

leetcode与数据结构---310,802