首页 > 代码库 > 并查集(判断一个图有几个连通块)
并查集(判断一个图有几个连通块)
import java.util.Scanner; // 并查集 判断一个图中有几个联通块 public class UnionFind { private int[] father;// private int count;// 分量数量 public UnionFind(int N){ count=N; father=new int[N]; for(int i=0;i<N;i++){ father[i]=i; } } public int count() { return count; } public boolean connected(int p,int q){ return father[p]==father[q]; } public int find(int p){ /*if(p!=father[p]){ father[p]=find(father[p]); } return father[p];*/ while(p!=father[p]){ p=father[p]; } return p; } public void union(int p,int q){ int proot=find(p); int qroot=find(q); if(proot==qroot) return; father[proot]=qroot;// 直接将p挂载到q count--; } public static void main(String[] args) { Scanner cin=new Scanner(System.in); int N=cin.nextInt(); UnionFind uf=new UnionFind(N); System.out.println(N+" nodes"); int M=cin.nextInt(); System.out.println(M+" edges"); while(M-->0){ int p=cin.nextInt(); int q=cin.nextInt(); // 若p q 已经在同一块中,则不需要采取任何行动 if(uf.connected(p,q)) continue; uf.union(p,q); System.out.println(p+" "+q); } System.out.println(uf.count()+" components"); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。