lintcode-178-图是否是树

178-图是否是树

给出 n 个节点，标号分别从 0 到 n - 1 并且给出一个无向边的列表 (给出每条边的两个顶点), 写一个函数去判断这张｀无向｀图是否是一棵树

注意事项

你可以假设我们不会给出重复的边在边的列表当中. 无向边　[0, 1] 和 [1, 0]　是同一条边，因此他们不会同时出现在我们给你的边的列表当中。

样例

给出n = 5 并且 edges = [[0, 1], [0, 2], [0, 3], [1, 4]], 返回 true.

给出n = 5 并且 edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], 返回 false.

标签

Union Find 深度优先搜索宽度优先搜索脸书谷歌 Zenefits

思路

若图是一棵树，需满足以下条件参考http://blog.csdn.net/waltonhuang/article/details/52103401：

边的个数 = 点的个数 - 1
不存在回路（dfs过程中如果碰到访问过的节点(当然这个节点不能是来时的节点)，就是有回路）
不存在孤立节点

code

class Solution {

public:

    /**

     * @param n an integer

     * @param edges a list of undirected edges

     * @return true if it's a valid tree, or false

     */

    bool validTree(int n, vector<vector<int>>& edges) {

        // Write your code here

        int size = edges.size(), i = 0;

        // 如果图中边的个数不等于点的个数n-1，必然不为树

        if (n - size != 1) {

            return false;

        }

        // 由 edges 得邻接表

        vector<vector<int>> neighbor(n);

        for (i = 0; i < size; i++) {

            int start = edges[i][0], end = edges[i][1];

            neighbor[start].push_back(end);

            neighbor[end].push_back(start);

        }

        // 检测是否有回路

        vector<bool> visited(n, false);

        if (hasCycle(neighbor, visited, -1, 0)) {

            return false;

        }

        // 检测是否有孤立节点

        for (i = 0; i < n; i++) {

            if (visited[i] == false) {

                return false;

            }

        }

        return true;

    }

    bool hasCycle(vector<vector<int>> &neighbor, vector<bool> &visited, int par, int kid) {

        if (visited[kid] == true) {

            return true;

        }

        visited[kid] = true;

        for (int i = 0; i < neighbor[kid].size(); i++) {

            // 先排除 par == neighbor[kid][i] 的情况，这种情况其实是neighbor数组定义的时候固有的特性，不算成环

            if (par != neighbor[kid][i] && hasCycle(neighbor, visited, kid, neighbor[kid][i])) {

                return true;

            }

        }

        return false;

    }

};

巴特西

lintcode-178-图是否是树

178-图是否是树

注意事项

样例

标签

思路

code

最新文章

热门文章