(拓扑排序11.3.1)POJ 1270 Following Orders(拓扑排序: 求变量串在约束组的作用下产生的有序集)

package com.njupt.acm;  
  
import java.util.Scanner;  
  
public class POJ_1270 {  
  
    public static int pre[];//入度序列  
    public static boolean has[];//标志序列  
    public static int N;//节点数  
    public static String var;//变量串  
    public static String v;//约束组串  
      
    public static void dfs(int dep,String res){//从长度为dep-1 的子序列res出发计算拓扑序列  
        if(dep == N + 1){  
            System.out.println(res);  
            return ;  
        }  
          
        for(int i = 'a' ; i <= 'z' ; ++i){  
            if(has[i] && pre[i] == 0){  
                has[i] = false;  
                for(int k = 0 ; k < v.length() ; k += 4){//删除约束组中所有入度为0的点的出边  
                    if(v.charAt(k) == i){  
                        --pre[v.charAt(k+2)];  
                    }  
                }  
                  
                dfs(dep+1,res+((char)i));  
                  
                for(int k = 0 ; k < v.length() ; k+=4){  
                    if(v.charAt(k) == i){  
                        ++pre[v.charAt(k+2)];  
                    }  
                }  
                has[i] = true;  
            }  
        }  
    }  
      
    public static void main(String[] args) {  
        Scanner scanner = new Scanner(System.in);  
        while(scanner.hasNextLine()){  
            pre = new int[1 << 8];  
            has = new boolean[1 << 8];  
              
            var = scanner.nextLine();  
            v = scanner.nextLine();  
            N = var.length()/2 + 1;//计算总结点数  
              
            for(int i = 0 ; i < var.length() ; i += 2){  
                has[var.charAt(i)] = true;  
            }  
              
            for(int i = 0 ; i < v.length() ; i += 4){//在每对约束组x y中,x的出度为1,y的入度为1  
                ++pre[v.charAt(i+2)];  
            }  
              
            dfs(1,"");  
            System.out.println();  
        }  
    }  
}