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"); } }
并查集(判断一个图有几个连通块),布布扣,bubuko.com
原文:http://blog.csdn.net/dutsoft/article/details/25506117