import java.util.*;

class Program {
    public boolean cycleInGraph(int[][] edges) {
        // Write your code here.
        int n = edges.length;
        boolean[] visited = new boolean[n];

        Arrays.fill(visited, false);

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;

            boolean containsCycle =
                helper(edges, i, visited);
            if (containsCycle) return true;
        }
        return false;
    }
    public boolean helper(int[][] edges, int i, boolean[] visited) {
        Set < Integer > set = new HashSet < > ();
        Stack < Map.Entry < Integer, Set < Integer >>> s = new Stack < > ();
        set.add(i);
        s.push(new AbstractMap.SimpleEntry < > (i, set));

        while (!s.isEmpty()) {
            Map.Entry < Integer, Set < Integer >> curr = s.pop();
            Set < Integer > path = curr.getValue();
            int node = curr.getKey();
            visited[node] = true;
            if (edges[node].length == 0) path.remove(node);
            for (int children: edges[node]) {
                if (visited[children] && path.contains(children)) {
                    return true;
                }
                Set < Integer > temp = new HashSet < > (path);
                temp.add(children);
                s.push(new AbstractMap.SimpleEntry < > (children, temp));
            }
        }
        return false;
    }
}

请确认时间和空间复杂度是O(V+E)和O(V)?

我使用了使用堆栈并将路径存储在堆栈中的迭代DFS.

我想要了解的是,在任何一点使用的空间是O(V).

推荐答案

不,空间复杂度不是O(?).对于给定的起始 node i,助手函数为其每个(非循环)后代存储从i到该后代的路径.在最坏的情况下,这可能代表O(??).

以下面的图表为例:

     1
    / \
   2   3
      / \
     4   5
        / \
       6   7
          / \
         8   ...
             ...
             /  \
          ?-1    ?

...并以i为根 node .然后,循环将在每次迭代中向堆栈添加两个 node ,并弹出一个 node ,直到到达 node ?.当它到达那里时,我们有一个带有?/2条目的堆栈(用even个数字表示 node ),每个条目都有一个集,其中包含根到 node 路径上的 node .所以这些集合的大小是2,3,4,5,...?/2

  <2, {1, 2}>
  <4, {1, 3, 4}>
  <6, {1, 3, 5, 6}>
  <8, {1, 3, 5, 7, 8}>
   ...

这些集合大小的总和是一个三角数,并且是O(??).

由于创建一组大小为?的时间复杂度为O(?)(请参见指定temp的语句),因此最坏情况下的时间复杂度也为O(??)=O(??).

Java相关问答推荐

Java:根据4象限中添加的行数均匀分布行的公式

如何在Java中声明未使用的变量?

Java 8中的多个字段和计数

CAMEL 4中的SAXParseException

使用动态ID从json获取详细信息的Jolt规范

如何确定springboot在将json字段转换为Dto时如何处理它?

Java编译器抛出可能未正确初始化的错误?

按属性值从流中筛选出重复项

JOOQ中的子查询使用的是默认方言,而不是配置的方言

如何对多个字段进行分组和排序?

尽管通过中断请求线程死亡,但线程仍将继续存在

Log4j与jdk21兼容吗?

有没有可能在时间范围内得到多种解决方案?

为什么StandardOpenOption.CREATE不能通过Ubuntu在中小企业上运行?

无法使用Java PreparedStatement在SQLite中的日期之间获取结果

在Java中使用StorageReference将数据从Firebase存储添加到数组列表

如何在MPAndroidChart中的条形图上正确添加标签

为什么当我输入变量而不是直接输入字符串时,我的方法不起作用?

声纳覆盖范围为 0%,未生成 jacoco.xml

如何使用 JDBC 更改 Postgres Enum 类型