popularcows.java

PKU中一些数据结构基本算法题的java实现

import java.util.*;

/**
 * ID:2186
 * MemoryLimitedExceed!
 * @author yhm
 *
 */
public class PopularCows {

	static boolean[] visit;
	static int[] number;
	static int[] branch;
	static int branch_id;
	static int num;
	static int size;
	static boolean[][] G;
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);

		while(cin.hasNext()){
			size = cin.nextInt();
			int M = cin.nextInt();
			G = new boolean[size][size];
			for(int i=0;i<size;i++){
				for(int j=0;j<size;j++){
					if(i==j){
						G[i][j] = true;
					}
					else{
						G[i][j] = false;
					}
				}
			}
			for(int i=0;i<M;i++){
				int A = cin.nextInt()-1;
				int B = cin.nextInt()-1;
				G[A][B] = true;
			}
			
			int r = solve();
			System.out.println(r);
			
		}

	}
	
	
	static int solve(){
		number = new int[size];
		visit = new boolean[size];
		Arrays.fill(visit, false);
		Arrays.fill(number, 0);
		num = 1;
		
		for(int i=0;i<size;i++){	
			if(!visit[i]){
				DFS_1(i);
				number[i] = num;
				num++;
			}
		}


		
		
		for(int i=0;i<size;i++){
			for(int j=i;j<size;j++){
				boolean temp = G[i][j];
				G[i][j] = G[j][i];
				G[j][i] = temp;
			}
		}
		
		branch = new int[size];
		branch_id = 0;
		num = 0;
		Arrays.fill(visit, false);
		while(num!=size){
			int maxIndex = 0;
			int max = 0;
			for(int i=0;i<size;i++){
				if(max<number[i] && !visit[i]){
					max = number[i];
					maxIndex = i;
				}
			}
			DFS_2(maxIndex);
			branch_id++;
		}
		int branch_num = branch_id;
		boolean[] degreeIsZero = new boolean[branch_num];
		Arrays.fill(degreeIsZero, true);
		
		for(int i=0;i<size;i++){
			for(int j=i;j<size;j++){
				boolean temp = G[i][j];
				G[i][j] = G[j][i];
				G[j][i] = temp;
			}
		}
		
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				if(G[i][j]){
					if(branch[i] != branch[j]){
						degreeIsZero[branch[i]] = false;
					}
				}
			}
		}
		
		int numOfZero = 0;
		int selectIndex = 0;
		for(int i=0;i<branch_num;i++){
			if(degreeIsZero[i]){
				numOfZero++;
				selectIndex = i;
			}
		}
		
		if(numOfZero!=1){
			return 0;
		}
		
		int result=0;
		for(int i=0;i<size;i++){
			if(branch[i]==selectIndex){
				result++;
			}
		}
		
		return result;
		
	}
	
	static void DFS_1(int n){
		visit[n] = true;
		for(int i=0;i<size;i++){
			if(G[n][i]){
				if(!visit[i]){
					DFS_1(i);
					number[i] = num;
					num++;
				}
			}
		}
	}

	static void DFS_2(int n){
		visit[n] = true;
		num++;
		branch[n] = branch_id;
		for(int i=0;i<size;i++){
			if(G[n][i]){
				if(!visit[i]){
					DFS_2(i);
				}
			}
		}
	}
	
	
}