拓扑排序算法实现

转载 作者：知者 更新时间：2024-03-12 12:45:57 26 4

package graph.topoSort;

import java.util.Scanner;
import java.util.Stack;

public class TopoSort {
    static final int maxn = 105;
    static int map[][] = new int[maxn][maxn];
    static int indegree[] = new int[maxn];
    static int topo[] = new int[maxn];
    static int n, m;
    static Stack<Integer> s = new Stack<>();

    static boolean TopoSort() { // 拓扑排序
        int cnt = 0;
        for (int i = 0; i < n; i++)
            if (indegree[i] == 0)
                s.push(i);
        while (!s.empty()) {
            int u = s.peek();
            s.pop();
            topo[cnt++] = u;
            for (int j = 0; j < n; j++)
                if (map[u][j] == 1)
                    if (--indegree[j] == 0)
                        s.push(j);
        }
        if (cnt < n) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();

        for (int i = 0; i < m; i++) {
            int u, v;
            u = scanner.nextInt();
            v = scanner.nextInt();
            map[u][v] = 1;
            indegree[v]++;
        }
        TopoSort();
        for (int i = 0; i < n - 1; i++)
            System.out.print(topo[i] + " ");
        System.out.println(topo[n - 1]);
    }
}

26 4 0

• kubernetes - 我们如何在图中可视化kubernetes对象/拓扑？

  是否可以可视化kubernetes拓扑并看到它在添加/删除/链接对象时实时更新？ 我在https://www.youtube.com/watch?v=38SNQPhsGBk上观看了一个视频，其中服务/

• hadoop - Hadoop中的 Rack 拓扑

  我在搜索 Rack 拓扑时发现了这个问题...可能是hadoop认证问题: 您的群集在三个不同的 Rack 中都有从属节点，并且您编写了一个 Rack 拓扑脚本，以将每台计算机分别识别为位于 Rack

• javascript - 如何动态添加链接到 d3 拓扑？

  我拿了sticky force layout示例并尝试添加额外链接并使用 enter() 更新布局，但随后所有链接都消失了，FireBug 也没有显示任何错误。 这些行不应该添加链接吗？ graph.

• zeromq - 右 ZeroMQ 拓扑

  我需要编写一个订单管理器，将客户(股票、外汇等)订单发送到适当的交易所。客户想要发送订单，但对 FIX 或其他专有协议(protocol)一无所知，只知道发送订单的内部(规范化)格式。我有应用程序(服

• java - 无法提交 Storm 拓扑

  我正在尝试使用 Eclipse 在远程主机上提交 Storm 拓扑。 这是我的代码: Config conf = new Config(); conf.setDebug(false); conf.se

• python - 将自定义开关类传递给 Mininet 拓扑

  这是一个名为 mininet 的流行网络模拟器的拓扑文件 我创建了一个 MultiSwitch() 类，我想将其传递给我的 Topology 类以用作默认开关 有没有办法做到这一点？我对Python不

• linux - 如何找到我的 CPU 拓扑？

  我从 cat/proc/cpuinfo 中了解到，我正在使用 Intel(R) Core(TM) i5 CPU M 560 @ 2.67GHz。但是我想知道确切的层次结构，比如有多少个套接字，每个套接

• apache-kafka - 如何在同一个实例上运行多个 Storm 拓扑？

  我正在学习storm。我对我们可以在 Apache Storm 上一次运行的拓扑数量有疑问。我已经在 Storm 集群上提交了两个拓扑，但一次只运行了一个拓扑。我需要杀死或停用已经存在的拓扑拓扑以运行

• masstransit - MassTransit 创建的 RabbitMQ 拓扑

  我正在尝试理解 topology of queues并交换 MT 在 RabbitMQ 中创建的。 我不能得到这两个陈述: we generate an exchange for each queue

• testing - 测试 Kafka Streams 拓扑

  我正在寻找一种方法来测试 Kafka Streams 应用程序。这样我就可以定义输入事件，测试套件会向我显示输出。 如果没有真正的 Kafka 设置，这可能吗？ 最佳答案 更新 Kafka 1.1.0

• java - 如何以编程方式终止 Apache Storm 拓扑？

  我正在使用 Java 类将拓扑提交到 Storm 集群，我还计划使用 Java 类来终止拓扑。但根据 Storm documentation ，以下命令用于终止拓扑并且没有 Java 方法(这是有正当

• hadoop - 如何在我的机器上运行 Storm 拓扑...使我的机器陷入 Storm

  Storm jar storm-starter-topologies-0.10.0-beta1.jar storm-starter-master.jar生产拓扑本地 我遇到了错误: Running:

• java - 如何在代码中使用新的 Bolt 更新现有的 Storm 拓扑？

  我正在编写一个 dockerized Java Spring 应用程序，该应用程序使用 Apache Storm v1.1.2、Kafka v0.11.0.1、Zookeeper 3.4.6、Eure

• java - 在 JavaFx 中使用 JTS 拓扑

  我在 jts 拓扑库中有一些多边形。如果我想在 javafx Pane 上绘图，我会这样做: Polygon poly=new Polygon();//javafx //g is geometry

• java - 如何动态地在 Java 中绘制(星形)拓扑？

  我需要在 Java GUI 应用程序中动态绘制(星形)拓扑。通过星形拓扑，我的意思是这样的: (来源:thebryantadvantage.com) 不需要太花哨，但我不想做得太丑陋和粗糙。我所说的动

• linux - 从 bash 脚本初始化 Mininet 拓扑

  我想自动化设置 Mininet 的过程虚拟机，通过 SSH 连接到 VM，在 VM 中启动 Mininet，并初始化拓扑。我需要 session 保持打开状态，以便我可以使用创建的网络向 Minine

• java - 使用 Java 代码重新平衡 Storm 拓扑

  我正在尝试重新平衡使用 KafkaSpout 的 Storm 拓扑。我的代码是: TopologyBuilder builder = new TopologyBuilder(); Pr

• performance - 如何在不使用 Web 仪表板的情况下分析 Apache Storm 拓扑？

  标题几乎说明了一切，我有一些 Storm 拓扑，我想测量它们的延迟，即来自 Kafka 的消息与最终相关执行的最后一点之间的时间量 bolt 。如果我可以深入研究结果以查看每个 bolt 之间的延迟，

• java - 更改 Kafka-streams 拓扑(添加重新分区步骤)对消息处理保证有影响吗

  假设我想让一些转换“A”可配置。此转换使用状态存储管理某些状态，并且还需要重新分区，这意味着仅在配置后才会进行重新分区。现在，如果我按照以下方式(或任何其他组合)运行应用程序 3 次(也可能是滚动升级

• java - 使用 shell bolt 构建 Storm 拓扑

  我目前正在尝试实现与 R 语言集成的 Storm 拓扑。 作为起点，我采用了以下项目 ( https://github.com/allenday/R-Storm )，它通过扩展 ShellBolt 类