[LeetCode] Graph Valid Tree [Union Find]

104828720 發布于2019-08-14 15:10 / 2681人閱讀

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.

Example

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Note

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Solution

public class Solution {
    
    int[] parents;
    public boolean validTree(int n, int[][] edges) {
        if (n-1 != edges.length) {
            return false;
        }
        parents = new int[n];
        //initialize n nodes as each own parent
        for (int i = 0; i < n; i++) {
            parents[i] = i;
        }
        for (int i = 0; i < n-1; i++) {
            if (find(edges[i][0]) == find(edges[i][1])) {
                return false; //if two nodes on edge[i] have the same parent, this edge makes a circle causing it invalid
            }
            else union(edges[i][0], edges[i][1]); //else union the two nodes on edge[i]
        }
        return true; 
    }
    public int find(int node) {
        //find the very first parent node, which is when the parent is the node itself
        if (parents[node] == node) {
            return node;
        }
        //find parent recursively
        return find(parents[node]);
    }
    public void union(int a, int b) {
        int finda = parents[a], findb = parent[b];
        //when node a and node b have different ancient parents, union them with the same parent
        if (finda != findb) {
            parents[finda] = findb;
        }
    }
}

Update 2018-10

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n-1) return false;
        int[] nums = new int[n];
        Arrays.fill(nums, -1);
        for (int i = 0; i < edges.length; i++) {
            int x = find(nums, edges[i][0]);
            int y = find(nums, edges[i][1]);
            if (x == y) return false;
            nums[x] = y;
        }
        return true;
    }
    private int find(int[] nums, int k) {
        if (nums[k] == -1) return k;
        else return find(nums, nums[k]);
    }
}

云服務器 GPU云服務器 union-find graph LeetCode graph編程語言

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65399.html

[Leetcode] Graph Valid Tree 圖與樹

摘要：這樣就將一個集合的節點歸屬到同一個集合號下了。最后如果并查集中只有一個集合，則說明可以構建樹。 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 w...

luqiuwen 2019-08-14 12:36 評論0 收藏0
[Leetcode] Graph Valid Tree 判斷一個圖是否為樹

摘要：只有一個連通分量還沒有環，就是樹，無根樹。無向圖邊的兩端是對稱的，無向圖講究連通這個概念，沒有方向，沒有拓撲，很像集合，所以非常適合用并查集來解決。并查集寫法參考注意方法用找的老大哥，合并的是的老大哥。 Graph Valid Tree Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each...

xbynet 2019-08-14 14:04 評論0 收藏0
261. Graph Valid Tree

摘要：題目鏈接檢查圖的連通性及是否有環，可以，，從一個點出發看能不能遍歷所有的點，同時來檢查是否有環。還可以用檢查是否有環，最后看的數量是否等于來判斷是不是。 261. Graph Valid Tree 題目鏈接：https://leetcode.com/problems... 檢查圖的連通性及是否有環，可以dfs，bfs，從一個點出發看能不能遍歷所有的點，同時visited來檢查是否有環。...

Jinkey 2019-08-16 10:29 評論0 收藏0
[LeetCode] 684. Redundant Connection

Problem In this problem, a tree is an undirected graph that is connected and has no cycles. The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one...

lncwwn 2019-08-16 13:55 評論0 收藏0
[LeetCode] 399. Evaluate Division

Problem Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the ...

BlackMass 2019-08-16 13:40 評論0 收藏0