吉林省长春市长春网站建设哪家好微信小商店怎么开

吉林省长春市长春网站建设哪家好,微信小商店怎么开,怎么开一个做网站的工作室,一个网站建设需求的人员一、思路#xff1a;#xff08;1#xff09;本题和684.冗余连接类似#xff0c;但本题是一个有向图#xff0c;相对要复杂一些。#xff08;2#xff09;题目要求#xff1a;有一个有向图#xff0c;是由一棵有向树 一条有向边组成的#xff08;所以此时这个图就不…一、思路1本题和684.冗余连接类似但本题是一个有向图相对要复杂一些。2题目要求有一个有向图是由一棵有向树 一条有向边组成的所以此时这个图就不能称之为有向树现在要求找到这条有向边并将其删除使得这个图可以恢复为有向树。3若有多条可以删除的边则删除顺序靠后的边。4有向树的性质对于一棵有向树只有根节点的入度为0其他节点的入度都为1因为该树除了根节点之外的每一个节点都有且只有一个父节点而根节点没有父节点。二、分情况讨论1.情况一找到入度为2的节点则直接删除一条指向该节点的边即可。如下图所示找到了节点3的入度为2删1-3或者2-3选择删顺序靠后的便可。2.情况二入度为2的节点还有一种情况如下图所示节点3的入度为2但在删除边的时候由于存在有向环只能删这条边节点1-节点3如果删除边节点4-节点3那么删除后本图也不是有向树了因为找不到根节点。综上所述如果遇到入度为2的节点需要判断删哪一条边删除后能使本图成为有向树。如果是删哪个都可以优先删顺序靠后的边。3.情况三如果没有入度为2的点说明图中有环注意是有向环且添加的边指向了根节点如下图所示此时删掉构成环的边即可。三、解决方法。1.首先计算每个节点的入度如果存在入度为2的节点就定位到该节点对应的两条边分别记为dup[0]和dup[1]。如果在删除dup[1]后剩余的边无法形成树说明dup[0]是需要删除的边否则说明dup[1]是需要删除的边。2.如果不存在入度为2的节点就遍历数组edges对于每条边u,v使用并查集维护节点之间的连通性。如果u和v已经连通说明图中存在有向环此时当前边即为需要删除的边。附代码class Solution { int[] parent; int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } void union(int x, int y) { if (find(x) ! find(y)) parent[find(y)] parent[x]; } public int[] findRedundantDirectedConnection(int[][] edges) { parent new int[1001]; int[] in new int[1001]; //记录每个节点的入度 int[] res {}; //存储可能的多余边 // 寻找是否存在入度为 2 的顶点 for (int[] e : edges) { if (in[e[1]] 2) { //如果某个节点的入度变为2 res e; //记录最后一条使入度变为2的边 } } // 如果存在入度为 2 的顶点 // 尝试删除指向该顶点的某一条边看剩下的点是否能够构成树 // 如果可以构成树直接返回该边否则返回另一条边 if (res.length ! 0) { if (check(edges, res)) return res; //如果删除res边后能成树则返回res else { //否则返回另一条指向同一个节点的边 for (int[] e : edges) if (e[1] res[1]) return e; } } // 重新初始化并查集 for (int i 0; i 1001; i) { parent[i] i; } for (int[] e : edges) { //如果两个节点已经在同一个集合说明这条边会成环 // 删除加入形成环的边 if (find(e[0]) find(e[1])) return e; else union(e[0], e[1]); } return new int[0]; } // 判断有向边构成的图形是否为树 boolean check(int[][] edges, int[] remove) { // 初始化并查集 for (int i 0; i 1001; i) { parent[i] i; } for (int[] e : edges) { // 跳过要删除的边 if (Arrays.equals(e, remove)) continue; // 如果删除后还有环说明删除的不是正确的边 if (find(e[0]) find(e[1])) return false; else union(e[0], e[1]); } return true; } }