popularcows1.java

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

import java.util.Arrays;
import java.util.Scanner;


/**
 * ID:2186
 * RuntimeError 理由未知！
 * @author yhm
 *
 */
public class PopularCows1 {

	static int maxV = 10000;
	
	static MyEdge[] edges = new MyEdge[maxV*6];
	static MyEdge[] edges_X= new MyEdge[maxV*6];
	static int N=0,M=0;
	static boolean[] visit = new boolean[maxV];
	static int[] number = new int[maxV];
	static int[] branch = new int[maxV];
	static int branch_id = 0;
	static int num=0;
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);

		N = cin.nextInt();
		M = cin.nextInt();
		for(int i=0;i<M;i++){
			int start = cin.nextInt()-1;
			int end = cin.nextInt()-1;
			edges[i] = new MyEdge(start, end);
			edges_X[i] = new MyEdge(end, start);
		}
		int r = solve();
		System.out.println(r);


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


		
		
		

		branch_id = 0;
		num = 0;
		Arrays.fill(branch, 0);
		Arrays.fill(visit, false);
		while(num!=N){
			int maxIndex = 0;
			int max = 0;
			for(int i=0;i<N;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<M;i++){
			int start = edges[i].start;
			int end = edges[i].end;
			if(branch[start] != branch[end]){
				degreeIsZero[branch[start]] = false;
			}
		}
		
		int numOfZero = 0;
		int selectIndex = 0;		
		int result=0;
		
		for(int i=0;i<branch_num;i++){
			if(degreeIsZero[i]){
				numOfZero++;
				selectIndex = i;
			}
		}
		
		if(numOfZero!=1){
			return 0;
		}
		
		for(int i=0;i<N;i++){
			if(branch[i]==selectIndex){
				result++;
			}
		}

		
		return result;
		
	}
	
	static void DFS_1(int n){
		visit[n] = true;
		for(int i=0;i<M;i++){
			if(edges[i].start==n){
				int end = edges[i].end;
				if(!visit[end]){
					DFS_1(end);
					number[end] = num;
					num++;
				}
			}
		}
	}

	static void DFS_2(int n){
		visit[n] = true;
		num++;
		branch[n] = branch_id;
		for(int i=0;i<M;i++){
			if(edges_X[i].start==n){
				int end = edges_X[i].end;
				if(!visit[end]){
					DFS_2(end);
				}
			}
		}
	}
	

}

class MyEdge{
	int start;
	int end;
	public MyEdge(int start, int end) {
		super();
		this.start = start;
		this.end = end;
	}
}