310. Minimum Height Trees
queue: degree为1的顶点
degree[ i ] : 和 i 顶点关联的边数。
先添加整个图，然后BFS删除每一层degree为1的节点。
class Solution { public List<Integer> findMinHeightTrees(int n, int[][] edges) { List<Integer> result = new ArrayList<>(); if(n == 1){ result.add(0); return result; } int[] degree = new int[n]; Map<Integer, List<Integer>> map = new HashMap<>(); for(int i = 0; i < n; i++) map.put(i, new ArrayList<>()); for(int[] pair : edges){ map.get(pair[0]).add(pair[1]); map.get(pair[1]).add(pair[0]); degree[pair[0]]++; degree[pair[1]]++; } Queue<Integer> queue = new LinkedList<>(); for(int i = 0; i < n; i++){ if(degree[i] == 1) queue.add(i); } while(!queue.isEmpty()){ List<Integer> list = new ArrayList<>(); int size = queue.size(); for(int i = 0; i < size; i++){ int cur = queue.poll(); list.add(cur); for(int nei : map.get(cur)){ degree[nei]--; if(degree[nei] == 1) queue.add(nei); } } result = list; } return result; } }
261. Graph Valid Tree
Union Find: 并查集，这种方法对于解决连通图的问题很有效，思想是我们遍历节点，如果两个节点相连，我们将其roots值连上，这样可以帮助我们找到环，我们初始化roots数组为-1，然后对于一个pair的两个节点分别调用find函数，得到的值如果相同的话，则说明环存在，返回false，不同的话，我们将其roots值union上
class Solution { public boolean validTree(int n, int[][] edges) { 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 edges.length == n - 1; } private int find(int[] nums, int i){ if(nums[i] == -1) return i; return find(nums, nums[i]); } }
<Graph> Topological + Undirected Graph 310 Union Find 261
原文：https://www.cnblogs.com/Afei-1123/p/12049612.html