课程表-拓扑排序
207：你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {//记录每个点的入度int[] indegrees = new int[numCourses];//记录每个点的出度List<List<Integer>> outdegrees = new ArrayList<>();//分配空间for(int i=0;i<numCourses;i++){outdegrees.add(new ArrayList<>());}//遍历，记录出度入度信息for(int[] item : prerequisites){int in = item[0];int out = item[1];indegrees[in]++;outdegrees.get(out).add(in);}LinkedList<Integer> queue = new LinkedList();//入度为0的点入队for(int i=0;i<numCourses;i++){if(indegrees[i]==0){queue.offer(i);}}while(!queue.isEmpty()){//入度为0的点int cur = queue.poll();numCourses--;//找他指向的点，这些点的入度-1for(int num:outdegrees.get(cur)){indegrees[num]--;//如果入度为0，加入队列if(indegrees[num]==0){queue.offer(num);}}}return numCourses==0;}
}课程表II - 拓扑排序
210：现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
class Solution {public int[] findOrder(int numCourses, int[][] prerequisites) {if(numCourses==0){return new int[0];}int[] indegree = new int[numCourses];List<List<Integer>> outdegree = new ArrayList<>();LinkedList<Integer> queue = new LinkedList<>();int[] res = new int[numCourses];int count = 0;for(int i=0;i<numCourses;i++){outdegree.add(new ArrayList<>());}for(int[] prerequisite : prerequisites){indegree[prerequisite[0]]++;outdegree.get(prerequisite[1]).add(prerequisite[0]);}for(int i=0;i<numCourses;i++){if(indegree[i]==0){queue.offer(i);}}while(!queue.isEmpty()){int start = queue.poll();res[count++]=start;for(int end : outdegree.get(start)){indegree[end]--;if(indegree[end]==0){queue.offer(end);}}}if(count==numCourses){return res;}return new int[0];}
}最小高度树-广度优先
310：可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
class Solution {public List<Integer> findMinHeightTrees(int n, int[][] edges) {List<Integer> res = new LinkedList<>();int[] visited = new int[n];if(n==1){res.add(0);return res;}ArrayList<ArrayList<Integer>> edge = new ArrayList<>();int[] degree = new int[n];LinkedList<Integer> queue = new LinkedList<>();for(int i=0;i<n;i++){edge.add(new ArrayList<>());}for(int[] edgeItem:edges){degree[edgeItem[0]]++;degree[edgeItem[1]]++;edge.get(edgeItem[0]).add(edgeItem[1]);edge.get(edgeItem[1]).add(edgeItem[0]);}for(int i=0;i<n;i++){if(degree[i]==1){queue.offer(i);}}while(!queue.isEmpty()){res = new LinkedList<>();int size = queue.size();for(int i=0;i<size;i++){int cur = queue.poll();visited[cur]=1;res.add(cur);for(int end:edge.get(cur)){if(visited[end]==0){degree[end]--;if(degree[end]==1){queue.offer(end);}}}}}return res;}
}冗余连接（删除图中的环的一边）
684：树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。
并查集
class Solution {public int[] findRedundantConnection(int[][] edges) {int length = edges.length;int[] parent = new int[length+1];for(int i=0;i<=length;i++){parent[i] = i;}for(int[] edge : edges){int start = edge[0];int end = edge[1];if(find(parent,start)!=find(parent,end)){union(parent,start,end);}else{return edge;}}return new int[0];}public void union(int[] parent,int index1,int index2){parent[find(parent,index1)] = parent[find(parent,index2)];}public int find(int[] parent,int index){if(parent[index]!=index){parent[index] = find(parent,parent[index]);}return parent[index];}
}判断图中是否有环
方法一：拓扑排序
无向图：
- 求出图中所有结点的度。
- 将所有度 <= 1 的结点入队。（独立结点的度为 0）
- 当队列不空时，弹出队首元素，把与队首元素相邻节点的度减一。如果相邻节点的度变为一，则将相邻结点入队。
- 循环结束时判断已经访问的结点数是否等于 n。等于 n 说明全部结点都被访问过，无环；反之，则有环。
有向图：
使用拓扑排序判断无向图和有向图中是否存在环的区别在于：
- 在判断无向图中是否存在环时，是将所有度 <= 1 的结点入队；
- 在判断有向图中是否存在环时，是将所有入度 = 0 的结点入队。
红蓝标记的图
zoom笔试：节点的颜色为红色或蓝色，当前节点的权值为根节点到当前节点路径上红蓝节点的数量差，求所有节点的权值之和。
先记录每个点的邻接点，再DFS遍历所有路径。遍历的时候，先判断当前节点的权值，再递归遍历邻接点。
public class Zoom {static int ans=0;public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = Integer.parseInt(sc.nextLine());String s = sc.nextLine();HashSet<Integer>[] edge = new HashSet[n+1];for(int i=0;i<=n;i++){edge[i] = new HashSet<>();}for(int i=0;i<n-1;i++){int firstNode = sc.nextInt();int secondNode = sc.nextInt();edge[firstNode].add(secondNode);edge[secondNode].add(firstNode);}int red=0,blue=0;dfs(edge,s,1,-1,red,blue);System.out.println(ans);HashMap<String,Integer> map = new HashMap<>();}public static void dfs(HashSet<Integer>[] edge,String str,int node,int lastNode,int red,int blue){if(str.charAt(node-1)=='R')red++;elseblue++;ans += Math.abs(red-blue);for(Integer end :edge[node]){if(end!=lastNode){dfs(edge,str,end,node,red,blue);}}}}