資訊專(zhuān)欄INFORMATION COLUMN
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.
ExampleGiven 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.
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.
Solutionpublic 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]);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/65399.html
摘要：這樣就將一個(gè)集合的節(jié)點(diǎn)歸屬到同一個(gè)集合號(hào)下了。最后如果并查集中只有一個(gè)集合，則說(shuō)明可以構(gòu)建樹(shù)。 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...
摘要：只有一個(gè)連通分量還沒(méi)有環(huán)，就是樹(shù)，無(wú)根樹(shù)。無(wú)向圖邊的兩端是對(duì)稱(chēng)的，無(wú)向圖講究連通這個(gè)概念，沒(méi)有方向，沒(méi)有拓?fù)?，很像集合，所以非常適合用并查集來(lái)解決。并查集寫(xiě)法參考注意方法用找的老大哥，合并的是的老大哥。 Graph Valid Tree Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each...
摘要：題目鏈接檢查圖的連通性及是否有環(huán)，可以，，從一個(gè)點(diǎn)出發(fā)看能不能遍歷所有的點(diǎn)，同時(shí)來(lái)檢查是否有環(huán)。還可以用檢查是否有環(huán)，最后看的數(shù)量是否等于來(lái)判斷是不是。 261. Graph Valid Tree 題目鏈接：https://leetcode.com/problems... 檢查圖的連通性及是否有環(huán)，可以dfs，bfs，從一個(gè)點(diǎn)出發(fā)看能不能遍歷所有的點(diǎn)，同時(shí)visited來(lái)檢查是否有環(huán)。...
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...
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 ...
閱讀 1921·2021-10-12 10:12
閱讀 2653·2021-09-29 09:42
閱讀 2935·2021-09-03 10:28
閱讀 2354·2019-08-30 15:54
閱讀 1241·2019-08-30 15:53
閱讀 1511·2019-08-30 11:26
閱讀 3515·2019-08-30 11:02
閱讀 2238·2019-08-30 11:02
