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

```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();
}
}
}
```