[LintCode] Graph Valid Tree

http://www.lintcode.com/en/problem/graph-valid-tree/

DFS 解法:

public class Solution {
    /**
     * @param n an integer
     * @param edges a list of undirected edges
     * @return true if it‘s a valid tree, or false
     */
    public boolean validTree(int n, int[][] edges) {
        // Write your code here
        if (n <= 0 || edges == null || n - 1 != edges.length) {
            return false;
        }
        int[][] matrix = new int[n][n];
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < edges.length; i++) {
            matrix[edges[i][0]][edges[i][1]] = 1;
            matrix[edges[i][1]][edges[i][0]] = 1;
        }
        dfs(matrix, 0, set);
        return set.size() == n;
    }

    private void dfs(int[][] matrix, int start, Set<Integer> set) {
        if (set.contains(start)) {
            return;
        }
        set.add(start);
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[start][i] == 1) {
                dfs(matrix, i, set);
            }
        }
    }
}

Union Find 解法:

public class Solution {
    /**
     * @param n an integer
     * @param edges a list of undirected edges
     * @return true if it‘s a valid tree, or false
     */
    class UnionFind {
        int[] id;
        int[] weight;
        public UnionFind(int n) {
            id = new int[n];
            weight = new int[n];
            for (int i = 0; i < n; i++) {
                id[i] = i;
                weight[i] = 1;
            }
        }
        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (weight[rootI] < weight[rootJ]) {
                id[rootI] = rootJ;
                weight[rootJ] += weight[rootI];
            } else {
                id[rootJ] = rootI;
                weight[rootI] += weight[rootJ];
            }
        }
        public int find(int i) {
            if (id[i] != i) {
                return find(id[i]);
            }
            return i;
        }
    }

    public boolean validTree(int n, int[][] edges) {
        if (n <= 0 || edges == null || n - 1 != edges.length) {
            return false;
        }
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < edges.length; i++) {
            if (uf.find(edges[i][0]) == uf.find(edges[i][1])) {
                return false;
            }
            uf.union(edges[i][0], edges[i][1]);
        }
        return true;
    }
}

这道题还可以用 BFS 解。

时间: 05-24

[LintCode] Graph Valid Tree的相关文章

Leetcode: Graph Valid Tree &amp;&amp; Summary: Detect cycle in directed graph and undirected graph

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. For example: Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return tru

[LeetCode#261] Graph Valid Tree

Problem: Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. For example: Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], r

[Swift]LeetCode261.图验证树 $ Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. For example: Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return tru

Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. Notice You can assume that no duplicate edges will appear in edges. Since all edg

LeetCode Graph Valid Tree

原题链接在这里:https://leetcode.com/problems/graph-valid-tree/ 题目: Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. For example: Given n

Graph Valid Tree -- LeetCode

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. For example: Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return tru

261. Graph Valid Tree

也是卡了好多天的题目 主要就是介绍了union-find的算法,用于检查Undirected graph有没有环 http://www.geeksforgeeks.org/union-find/ 1 public boolean validTree(int n, int[][] edges) { 2 int[] parent = new int[n]; 3 Arrays.fill(parent, -1); 4 for(int i = 0; i < edges.length ; i++) { 5

leetcode 261-Graph Valid Tree(medium)(BFS, DFS, Union find)

Given n nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. 这道题主要就是判断1.是否有环路 2. 是否是连通图 可以用DFS, BFS 和 Union find,union find最合适. 对于DFS和BFS,首先都是建立

[LintCode] Flatten Binary Tree to Linked List 将二叉树展开成链表

Flatten a binary tree to a fake "linked list" in pre-order traversal. Here we use the right pointer in TreeNode as the next pointer in ListNode. Notice Don't forget to mark the left child of each node to null. Or you will get Time Limit Exceeded