Leetcode1579. 保证图可完全遍历

左手的ㄟ右手 2023-01-12 04:23 85阅读 0赞

# Leetcode1579. 保证图可完全遍历 #

[题目链接][Link 1]

## 思路 ##

首先使用并查集检查Alice和Bob是否分别能够遍历整张图,如果一人不行则返回-1。然后，开始找两个人都能遍历的情况下的最小边，我们可以只当，两人都遍历的情况下最多的边数为2\*(n-1)其中n为顶点数。为了使边数减少，我们可以这样考虑如果存在公共边即类型3我们应将该边对应的两个结点合并，因为这样可以至少减少一条边(这是一种贪心思路)，我们这样考虑，如果存在一条公共边他们两个人在遍历图的时候一个人选了另外一个人没选，那么我们可以让没选的那个人加上这条边，则该人遍历图会形成环，然后将该人属于自己的边删去一条即可，这样就减少一条边。对于两个人都没写的情况也可以类似讨论。

## 代码 ##

class Solution {
        
        public int maxNumEdgesToRemove(int n, int[][] edges) {
        
        	//并查集解决
        	boolean isTravel=false;
        	unionFind unionfind=new unionFind(n+1);
        	for(int[] o:edges) {
        
        		if(o[0]==1 || o[0]==3) {
        
        			unionfind.union(o[1], o[2]);
        			if(unionfind.getSize()==n) {
        
        				isTravel=true;
        				break;
        			}
        		}
        	}
        	if(!isTravel) return -1;
        	isTravel=false;
        	unionfind.Init(n+1);
            for(int[] o:edges) {
        
        		if(o[0]==2 || o[0]==3) {
        
        			unionfind.union(o[1], o[2]);
        			if(unionfind.getSize()==n) {
        
        				isTravel=true;
        				break;
        			}
        		}
        	}
        	if(!isTravel) return -1;
        	//开始寻找少边 首先合并共同边 因为只有当两者都选择公共边时可以使得总用边数最小
        	unionfind.Init(n+1);
        	for(int[] o:edges) {
        
        		if(o[0]==3) {
        
        			unionfind.union(o[1], o[2]);
        		}
        	}
        	HashSet<Integer> hashset=new HashSet<Integer>(10001);
        	for(int i=1;i<=n;i++) {
        
        		hashset.add(unionfind.find(i));
        	}
        	int edgeNum=n-hashset.size();
        	edgeNum+=(hashset.size()-1)*2;
        	return edges.length-edgeNum;
        }
        class unionFind{
        
        	int[] parent;
        	int[] size;
        	unionFind(int n) {
        
        		parent=new int[n];
        		size=new int[n];
        		for(int i=0;i<n;i++) {
        
        			parent[i]=i;
        			size[i]=1;
        		}
        	}
        	//初始化
        	void Init(int n) {
        
        		for(int i=0;i<n;i++) {
        
        			parent[i]=i;
        			size[i]=1;
        		}
        	}
        	
        	int find(int x) {
        
        		if(x!=parent[x]) {
        
        			parent[x]=find(parent[x]);
        		}
        		return parent[x];
        	}
        	
        	boolean union(int x,int y) {
        
        		int rootX=find(x);
        		int rootY=find(y);
        		if(rootX==rootY) return false;
        		parent[rootY]=rootX;
        		size[rootX]+=size[rootY];
        		return true;
        	}
        	//返回子集数量
        	int getSize() {
        
        		return size[find(1)];
        	}
        }
    }

[Link 1]: https://leetcode-cn.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/