Leetcode1489. 找到最小生成树里的关键边和伪关键边

刺骨的言语ヽ痛彻心扉 2022-11-19 09:42 12阅读 0赞

# Leetcode1489. 找到最小生成树里的关键边和伪关键边–简单的枚举法 #

## 基本思路 ##

首先找到一颗最小生成树,记录这颗树的权值,然后我们在分别判断每条边是否为关键边或者伪关键边。

#### 判断是否为为关键边思路 ####

首先将第i条边从图中删去,然后尝试构造最小生成树。如果生成的最小生成树的权值大于我们构造的第一颗最小生成树或者根本无法构成树,那么我们认为这条边是关键边。

#### 判断是否为伪关键边的思路 ####

因为我们在之前已经判断出在第i条边不加入时可以构成最小生成树（否则在判断其为关键边时已经退出）。故我们接下来可以直接将第i条边加入那么依然可以生成一棵树。我们在加入该边的情况下依旧使用贪心构造已加入该边的最小树，如果生成的树的权值与第一颗最小生成树相同那么该边即非关键边，否则不是。

## 代码实现 ##

class Solution {
        
       public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        
       	//做预处理 对每条边加上编号
       	int m=edges.length;
       	int[][] newEdges=new int[m][4];
       	for(int i=0;i<m;i++) {
        
       		for(int j=0;j<3;j++) {
        
       			newEdges[i][j]=edges[i][j];
       		}
       		newEdges[i][3]=i;
       	}
       	//将边权值按从小到达的顺序排序
       	Arrays.sort(newEdges,new Comparator<int[]>() {
        
       		public int compare(int[] x,int []y) {
        
       			return x[2]-y[2];
       		}
       	});
       	//开始查找第一颗最小生成树
       	unionFind firstTree=new unionFind(n);
       	int val=0;  //记录最小生成树所有边的权值
       	for(int i=0;i<m;i++) {
        
       		if(firstTree.union(newEdges[i][0], newEdges[i][1])) {
        
       			val+=newEdges[i][2];
       		}
       	}
       	
       	List<List<Integer>> ret=new ArrayList<List<Integer>>();
       	for(int i=0;i<2;i++) {
        
       		ret.add(new ArrayList<Integer>());
       	}
       	//开始使用枚举找到所有最小生成树
       	for(int i=0;i<m;i++) {
          //判断第i条边是否为关键边或者伪关键边
       		unionFind minTree=new unionFind(n);
       		int curVal=0;
       		//判断第i条边是否为关键边 基本思路如下
       		/*
       		 * 首先将第i条边从图中删去,然后尝试构造最小生成树
       		 * 如果生成的最小生成树的权值大于我们构造的第一颗最小生成树
       		 * 或者根本无法构成树,那么我们认为这条边是关键边
       		 */
       		for(int j=0;j<m;j++) {
        
       			if(i!=j && minTree.union(newEdges[j][0], newEdges[j][1])) {
        
       				curVal+=newEdges[j][2];
       			}
       		}
       		if(curVal!=val || minTree.edgeNum<n-1) {
        
       			ret.get(0).add(edges[i][3]);
       			continue;
       		}
       		//开始判断这条边是否为非关键边 基本思路如下
       		/*
       		 * 因为我们在之前已经判断出在第i条边不加入时可以构成最小生成树
       		 * 故我们接下来可以直接将第i条边加入 那么依然可以生成一棵树
       		 * 我们在加入该边的情况下依旧使用贪心构造已加入该边的最小树
       		 * 如果生成的树的权值与第一颗最小生成树相同 那么该边即非关键边
       		 */
       		minTree=new unionFind(n);
       		curVal=0;
       		minTree.union(newEdges[i][0], newEdges[i][1]);
       		curVal+=newEdges[i][2];
       		for(int j=0;j<m;j++) {
        
       			if(minTree.union(newEdges[j][0], newEdges[j][1])) {
        
       				curVal+=newEdges[j][2];
       			}
       		}
       		if(curVal==val) ret.get(1).add(newEdges[i][3]);
       	}
       	return ret;
       }
       //简单的并查集模板
       class unionFind{
        
       	int[] parent;
       	public int edgeNum;
       	unionFind(int n){
        
       		edgeNum=0;
       		parent=new int[n];
       		for(int i=0;i<n;i++) {
        
       			parent[i]=i;
       		}
       	}
       	boolean union(int x,int y) {
        
       		int rootX=find(x);
       		int rootY=find(y);
       		if(rootX==rootY) return false;
       		parent[rootY]=rootX;
       		edgeNum++;  //边数+1
       		return true;
       	}
       	
       	int find(int x) {
        
       		if(x!=parent[x]) {
        
       			parent[x]=find(parent[x]);
       		}
       		return parent[x];
       	}
       }
    }