频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
(拓扑排序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();  
        }  
    }  
}  

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 拓扑 变量 作用
上一篇: N-Queens II @LeetCode
下一篇:HttpURLConnection,getResponseCode,网络超时 相关总结。
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站