leetcode 力扣 1442 连通网络的操作次数 题解 算法题

题目:连通网络的操作次数用以太网线缆将n0n-1。线缆connectionsconnections[i[ab连接了计算机a和b。网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。connections，你可以拔开任意两台直连计算机之所需的最少操作次数。如果不可能，则返回-1。示例1：输入：n=4,connections=[[0,1],[0,2],[1,2]]输出：1解释：拔下计算机1和2之间的线缆，并将它插到计算机1和3上。示例2：输入：n=6,connections=[[0,1],[0,2],[0,3],[1,2],[1,3]]输出：2示例3：输入：n=6,connections=[[0,1],[0,2],[0,3],[1,2]]输出：-1解释：线缆数量不足。示例4：输入：n=5,connections=[[0,1],[0,2],[3,4],[2,3]]输出：0提示：1<=n<=10^51<=connections.length<=min(n*(n-1)/2,10^5)connections[i].length==20<=connections[i][0],connections[i][1]<nconnections[i][0]!=connections[i][1]没有重复的连接。两台计算机不会通过多条线缆连接。语言:C++classSolution{private:vector<vector< vector< int>used;public:voiddfs(intu){used[u]= for(intv:edges[u]){if(!used[v]){dfs(v);}}}intmakeConnected(intn,vector<vector<int>>&connections){if(connections.size()<n- 1){return-1;}edges.resize(n);for(constauto&conn:connections){edges[conn[ 0]].push_back(conn[1]);edges[conn[ 1]].push_back(conn[0]);}used.resize(n);intans= for(inti=0;i<n;++i){if(!used[i]){dfs(i);++ans;}}returnans-1;}};语言:C++//并查集模板classUnionFind{public:vector< vector< int>size;intn;//当前连通分量数目intsetCount;public:UnionFind( int_n):n(_n),setCount(_n),parent(_n),size(_n, 1){iota(parent.begin(),parent.end(), 0);}intfindset(intx){returnparent[x]==x?x:parent[x]=findset(parent[x]);}boolunite(intx,inty){x=findset(x);y=findset(y);if(x==y){returnfalse;}if(size[x]<size[y]){swap(x,y);}parent[y]=x;size[x]+=size[y];--setCount;returntrue;}boolconnected(intx,inty){x=findset(x);y=findset(y);returnx==y;}};classSolution{public:intmakeConnected(intn,vector<vector<int>>&connections){if(connections.size()<n- 1){return-1;}UnionFinduf(n);for(constauto&conn:connections){uf.unite(conn[ 0],conn[1]);}returnuf.setCount- 1;}};语言:JavaclassSolution{List<Integer>[]edges;boolean[]used;publicintmakeConnected(intn,int[][]connections){if(connections.length<n- 1){return-1;}edges= newList[n];for(inti=0;i<n;++i){edges[i]= newArrayList<Integer>();}for(int[]conn:connections){edges[conn[ 0]].add(conn[1]);edges[conn[ 1]].add(conn[0]);}used= newboolean[n];intans= 0;for(inti=0;i<n;++i){if(!used[i]){dfs(i);++ans;}}returnans-1;}publicvoiddfs(intu){used[u]= true;for(intv:edges[u]){if(!used[v]){dfs(v);}}}}语言:JavaclassSolution{publicintmakeConnected(intn,int[][]connections){if(connections.length<n- 1){return-1;}UnionFinduf= newUnionFind(n);for(int[]conn:connections){uf. unite(conn[0],conn[1]);}returnuf.setCount-1;}}//并查集模板classUnionFind{int[]parent;int[]size;intn;//当前连通分量数目intsetCount;publicUnionFind(intn){this.n=n;this.setCount=n;this.parent=newint[n];this.size=newint[n];Arrays. fill(size,1);for(inti=0;i<n;++i){parent[i]=i;}}publicintfindset(intx){returnparent[x]==x?x:(parent[x]= findset(parent[x]));}publicbooleanunite(intx,inty){x= findset(x);y= findset(y);if(x==y){returnfalse;}if(size[x]<size[y]){inttemp=x;x=y;y=temp;}parent[y]=x;size[x]+=size[y];--setCount;returntrue;}publicbooleanconnected(intx,inty){x= findset(x);y= findset(y);returnx==y;}}语言:PythonclassSolution:defmakeConnected(self,n:int,connections:List[List[int]]) ->int:iflen(connections)<n-1:return-1edges =collections.defaultdict(list)forx,y edges[x].append(y)edges[y].append(x)seen =set()defdfs(u:int):seen.add(u)forvinedges[u]:ifvnotinseen:dfs(v)ans =0foriinrange(n):ifinotinseen:dfs(i)ans +=1returnans-1语言:Python#并查集模板classUnionFind:definit(self,n:int):self.parent=list(range(n))self.size=[1]*nself.n=n#当前连通分量数目self.setCount=ndeffindset(self,x:int) ->int:ifself.parent[x]==x:returnxself.parent[x]=self.findset(self.parent[x])returnself.parent[x]defunite(self,x:int,y:int) ->bool:x,y =self.findset(x),self.findset(y)ifx==y:returnFalseifself.size[x]<self.size[y]:x,y =y,xself.parent[y]=xself.size[x]+=self.size[y]self.setCount-=1returnTruedefconnected(self,x:int,y:int) ->bool:x,y =self.findset(x),self.findset(y)returnx==yclassSolution:defmakeConnected(self,n:int,connections:List[List[int]]) ->int:iflen(connections)<n-1:return-1uf =UnionFind(n)forx,y uf.unite(x,y)returnuf.setCount-1语言:JavaScriptvarmakeConnected=function(n,connections){if(connections.length<n-1){return-1;}constedges=newMap();for(const[x,y]ofconnections){edges .get(x)?edges.get(x).push(y):edges.set(x,[y]);edges .get(y)?edges.get(y).push(x):edges.set(y,[x]);}constused=newArray(n).fill(0);letans=0;for(leti=0;i<n;i++){if(!used[i]){dfs(i,used,edges);ans ++;}}returnans-1;};constdfs=(u,used,edges)=>{used[u] =1;if(edges.get(u)){for(constvofedges.get(u)){if(!used[v]){dfs(v,used,edges);}}}}语言:JavaScriptvarmakeConnected=function(n,connections){if(connections.length<n-1){return-1;}constuf=newUnionFind(n);for(constconnofconnections){uf .unite(conn[0],conn[1]);}returnuf.setCount-1;};//并查集模板classUnionFind{constructor(n){this.parent=newArray(n).fill(0).map((element,index)=>index);this.size=newArray(n).fill(1);//当前连通分量数目this.setCount=n;}findset(x){if(this.parent[x]===x){returnx;}this.parent[x]=this.findset(this.parent[x]);returnthis.parent[x];}unite(a,b){letx=this.findset(a),y=this.findset(b);if(x===y){returnfalse;}if(this.size[x]<this.size[y]){[x ,y]=[y,x];}this.parent[y]=x;this.size[x]+=this.size[y];this.setCount-=1;returntrue;}connected(a,b){constx=this.findset(a),y=this.findset(b);returnx===y;}}语言:gofuncmakeConnected(nint,connections[][]int)(ansint){iflen(connections)<n -1{return-1}graph:=make([][] int,n)for_,c:= v,w:=c[ 0],c[1]graph[v]=append(graph[v],w)graph[w]=append(graph[w],v)}vis:=make([] bool,n)vardfsfunc(int)dfs= func(fromint){vis[from]= truefor_,to:= if!vis[to]{dfs(to)}}}fori,v:= if!v{ans++dfs(i)}}returnans- 1}语言:gotypeunionFindstruct{parent,size[] intsetCount int//当前连通分量数目}funcnewUnionFind(nint)*unionFind{parent:=make([] int,n)size:=make([] int,n)fori:=rangeparent{parent[i]=isize[i]= 1}return&unionFind{parent,size,n}}func(uf*unionFind)find(x int)int{ifuf.parent[x]!=x{uf.parent[x]=uf.find(uf.parent[x])}returnuf.parent[x]}func(uf*unionFind)union(x,y fx,fy:=uf.find(x),uf.find(y)iffx==fy{return}ifuf.size[fx]<uf.size[fy]{fx,fy=fy,fx}uf.size[fx]+=uf.size[fy]uf.parent[fy]=fxuf.setCount--}funcmakeConnected(nint,connections[][]int)int{iflen(connections)<n -1{return-1}uf:=newUnionFind(n)for_,c:= uf.union(c[ 0],c[1])}returnuf.setCount- 1}语言:phpclassSolution{public$xu=0;/**@paramInteger$n@paramInteger[][]$connections@returnInteger*/publicfun