thebottomofagraph_1.java

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

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

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

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


		
		while(cin.hasNext()){
			N = cin.nextInt();
			if(N == 0){
				break;
			}
			M = cin.nextInt();
			edges = new Edge[M];
			edges_X= new Edge[M];
			for(int i=0;i<M;i++){
				int start = cin.nextInt()-1;
				int end = cin.nextInt()-1;
				edges[i] = new Edge(start, end);
				edges_X[i] = new Edge(end, start);
			}
			solve();
		}


	}
	
	
	static void solve(){		
		number = new int[N];
		visit = new boolean[N];
		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;
		branch = new int[N];
		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;
			}
		}
		
		StringBuffer result = new StringBuffer("");
		for(int i=0;i<N;i++){
			if(degreeIsZero[branch[i]]){
				result.append(i+1);
				if(i!=N-1){
					result.append(" ");
				}
			}
		}
		System.out.println(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 Edge{
	int start;
	int end;
	public Edge(int start, int end) {
		super();
		this.start = start;
		this.end = end;
	}
}