频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
HDU1285(拓扑排序(模板))
2012-08-01 09:40:46           
收藏   我要投稿

拓扑排序:
思想:1、在有向图中选择一个没有前驱的顶点并且输出
2、从图中删除该节点和所有以它为尾的弧。
重复上述步骤,知道全部顶点都已经输出,或者当前图中不存在无前驱的顶点为止。后面一种情况说明有向图中存在环。
HDU1285:https://acm.hdu.edu.cn/showproblem.php?pid=1285
[java] 
package D0731; 
 
import java.util.*; 
 
//图谱排序(邻接矩阵实现图存储) 
public class HDU1285_2 { 
 
    static int n, m; 
    static int[] indegree;// 顶点的入度 
    static int[] result;// 保存最后排好序的结果 
    static int[][] G;// 邻接矩阵存储 
    static Queue<Integer> que; 
 
    public static void main(String[] args) { 
        Scanner sc = new Scanner(System.in); 
        while (sc.hasNext()) { 
            n = sc.nextInt(); 
            m = sc.nextInt(); 
            G = new int[n + 1][n + 1]; 
            indegree = new int[n + 1]; 
 
            while (m-- > 0) { 
                int u = sc.nextInt(); 
                int v = sc.nextInt(); 
                if (G[u][v] == 0) {// 这个条件一定要,否则WA,避免重边的情况比如a b可能出现两次的情况 
                    indegree[v]++; 
                    G[u][v] = 1; 
                } 
            } 
            topsort(); 
            // 输出 
            System.out.print(result[1]); 
            for (int i = 2; i <= n; i++) { 
                System.out.print(" "+result[i]); 
            } 
            System.out.println(); 
        } 
    } 
 
    private static void topsort() { 
        result = new int[n + 1]; 
        que = new PriorityQueue<Integer>(); 
        int index = 0; 
        for (int i = 1; i <= n; i++) { 
            if (indegree[i] == 0) 
                que.add(i); 
        } 
        while (!que.isEmpty()) { 
            int u = que.poll(); 
            result[++index] = u; 
            for (int i = 1; i <= n; i++) { 
                if (G[u][i] == 1) { 
                    indegree[i]--; 
                    if (indegree[i] == 0) 
                        que.add(i); 
                } 
            } 
        } 
    } 
 

 
 
[java]
package D0731; 
 
import java.util.*; 
 
//拓扑排序(使用邻接表实现) 
public class HDU1285_3 { 
 
    static int n, m; 
    static int[] indegree;// 顶点的入度 
    static int[] result;// 保存最后排好序的结果 
    static List<ArrayList<Integer>> G;// 邻接表。 
    static Queue<Integer> que; 
 
    public static void main(String[] args) { 
        Scanner sc = new Scanner(System.in); 
        while (sc.hasNext()) { 
            n = sc.nextInt(); 
            m = sc.nextInt(); 
            G = new ArrayList<ArrayList<Integer>>(); 
            for(int i = 1;i<=n+1;i++) 
                G.add(new ArrayList<Integer>()); 
            indegree = new int[n + 1]; 
            while (m-- > 0) { 
                int u = sc.nextInt(); 
                int v = sc.nextInt(); 
                if (!G.get(u).contains(v)) {// 这个条件一定要,否则WA,避免重边的情况比如a b可能出现两次的情况 
                    indegree[v]++; 
                    G.get(u).add(v); 
                } 
            } 
            topsort(); 
            // 输出 
            System.out.print(result[1]); 
            for (int i = 2; i <= n; i++) { 
                System.out.print(" " + result[i]); 
            } 
            System.out.println(); 
        } 
    } 
 
    private static void topsort() { 
        result = new int[n + 1]; 
        que = new PriorityQueue<Integer>(); 
        int index = 0; 
        for (int i = 1; i <= n; i++) { 
            if (indegree[i] == 0) 
                que.add(i); 
        } www.2cto.com
        while (!que.isEmpty()) { 
            int v = que.poll(); 
            result[++index] = v; 
            for (int i : G.get(v)) { 
                indegree[i]--; 
                if (indegree[i] == 0) 
                    que.add(i); 
            } 
        } 
    } 
 

作者:lhfight

点击复制链接 与好友分享!回本站首页
相关TAG标签 拓扑 模板
上一篇:java actor模型和消息传递简单示例
下一篇:java基础知识
相关文章
图文推荐
文章
推荐
点击排行

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

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