thebottomofagraph.java

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

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


/**
 * ID:2553
 * 强连通分支。邻接矩阵，AC
 * @author yhm
 *
 */
public class TheBottomofaGraph {

	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();
			if(size==0){
				break;
			}
			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;
			}
			
			solve();
			
		}

	}
	
	
	static void 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;
					}
				}
			}
		}
		
		
		StringBuffer result = new StringBuffer("");
		for(int i=0;i<size;i++){
			if(degreeIsZero[branch[i]]){
				result.append(i+1);
				if(i!=size-1){
					result.append(" ");
				}
			}
		}
		System.out.println(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);
				}
			}
		}
	}

}