leetcode：省份数量_leetcode 省份数量

package com.lz.third;
 
import java.util.LinkedList;
import java.util.Queue;
 
public class GroupMerge {
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//System.out.println(getProvince(new int[][] {{1,0,0},{0,1,0},{0,0,1}}));
		//System.out.println(getProvince(new int[][] {{1,1,0},{1,1,0},{0,0,1}}));
		//System.out.println(getProvince1(new int[][] {{1,0,0},{0,1,0},{0,0,1}}));
		//System.out.println(getProvince1(new int[][] {{1,1,0},{1,1,0},{0,0,1}}));
		System.out.println(getProvince2(new int[][] {{1,0,0},{0,1,0},{0,0,1}}));
		System.out.println(getProvince2(new int[][] {{1,1,0},{1,1,0},{0,0,1}}));
	}
 
	//深度优先
	private static int getProvince(int[][] isConnected) {
		int cities=isConnected[0].length;
		boolean[] visited=new boolean[cities];
		int provinces=0;
		for(int i=0;i<cities;i++) {
			if(!visited[i]) {
				dfs(i,cities,visited,isConnected);
				provinces++;
			}
		}
		return provinces;
	}
	public static void dfs(int i,int cities,boolean[] visited,int[][] isConnected) {
		for(int j=0;j<cities;j++) {
			if(isConnected[i][j]==1&&!visited[j]) {
				visited[j]=true;
				dfs(j,cities,visited,isConnected);
			}
		}
	}
	
	//广度优先
	private static int getProvince1(int[][] isConnected) {
		int cities=isConnected[0].length;
		boolean[] visited=new boolean[cities];
		int provinces=0;
		Queue<Integer> queue=new LinkedList<Integer>();
		for(int i=0;i<cities;i++) {
			if(!visited[i]) {	
				queue.offer(i);
				while(!queue.isEmpty()) {
					int k=queue.poll();
					visited[k]=true;
					for(int j=i+1;j<cities;j++) {
						if(isConnected[i][j]==1&&!visited[j]) {
							queue.offer(j);
						}
					}
				}
				provinces++;
			}
		}
		return provinces;
	}
	
	//并查集
	private static int getProvince2(int[][] isConnected) {
		int cities=isConnected[0].length;
		int[] head=new int[cities];
		int[] level=new int[cities];
		for(int i=0;i<cities;i++) {
			head[i]=i;
			level[i]=1;
		}
		for(int i=0;i<cities;i++) {
			for(int j=i+1;j<cities;j++) {
				if(isConnected[i][j]==1) {
					merge(i,j,head,level);
				}
			}
		}
		int count=0;
		for(int i=0;i<cities;i++) {
			if(head[i]==i) {
				count++;
			}
		}
		return count;
	}	
	public static void merge(int x,int y,int[] head,int[] level) {
		int i=find(x,head);
		int j=find(y,head);
		if(i==j) {
			return;
		}
		if(level[i]<=level[j]) {
			head[i]=j;
		}else {
			head[j]=i;
		}
		level[j]++;
	}
	public static int find(int x,int[] head){	
		if(head[x]==x) {
			return x;
		}
		head[x]=find(head[x],head);
		return head[x];
	}
	
 
}