algorithm - 为什么 DFS 在检查图是否为树时速度不够快

标签 algorithm graph tree pascal

我试图解决这个问题 Problem Description 似乎正确的想法是检查给定的图是否有循环(是否是树)。但是,我的代码无法通过测试 7(总是超出时间限制),知道如何让它更快吗?我用的是DFS。非常感谢 是的,终于被录取了。问题是每个顶点上的 dfs,这是不必要的。 dfs 函数应该是这样的。

function dfs(idx: integer; id: integer): boolean;
begin
  if (visited[idx] = id) then
  begin
    Result := false;
    Exit;
  end;
  if (tree[idx] <> 0) then
  begin
    visited[idx] := id;
    Result := dfs(tree[idx], id);
    Exit;
  end;
  Result := true;
end;



program Project2;

{$APPTYPE CONSOLE}

var
  i, m, j, n, k: integer;
  tree: array [1 .. 25001] of integer;
  visited: array [1 .. 25001] of boolean;

function dfs(idx: integer): boolean;
label
  fin;
var
  buf: array[1 .. 25001] of integer;
  i, cnt: integer;
begin
  cnt := 1;
  while (true) do
  begin
    if (visited[idx]) then
    begin
      Result := false;
      goto fin;
    end;
    if (tree[idx] <> 0) then
    begin
      visited[idx] := true;
      buf[cnt] := idx;
      Inc(cnt);
      idx := tree[idx];
    end
    else
    begin
      break;
    end;
  end;
  Result := true;
fin:
  for i := 1 to cnt - 1 do
  begin
    visited[buf[i]] := false;
  end;
end;

function chk(n: integer): boolean;
var
  i: integer;
begin
  for i := 1 to n do
  begin
    if (tree[i] = 0) then continue;
    if (visited[i]) then continue;
    if (dfs(i) = false) then
    begin
      Result := false;
      Exit;
    end;
  end;
  Result := true;
end;

begin
  Readln(m);
  for i := 1 to m do
  begin
    Readln(n);
    k := 0;
    for j := 1 to n do
    begin
      Read(tree[j]);
      if (tree[j] = 0) then
      begin
        Inc(k);
      end;
    end;
    if (k <> 1) then
    begin
      Writeln('NO');
    end
    else
    if (chk(n)) then
    begin
      Writeln('YES');
    end
    else
    begin
      Writeln('NO');
    end;
    Readln;
  end;
  //Readln;
end.

最佳答案

我对 Pascal 几乎一无所知,所以我可能会误解你在做什么,但我认为罪魁祸首是在 fin 你取消标记访问顶点的地方。这迫使您从每个顶点执行 DFS,而您只需要为每个组件执行一个。

如果连接的组件不止一个,则运动将停止

  • 因为一个顶点指向一个已经标记的顶点,在这种情况下我们只是因为找到了一个循环而停止
  • 因为顶点没有指向任何人(但它本身),在这种情况下我们需要找到下一个未标记的顶点并从那里再次开始另一个 DFS

你不必担心回溯的簿记,因为在这个问题中每个顶点最多指向另一个顶点。也无需担心哪个 DFS 做了哪个标记,因为无论如何每个 DFS 都只会在其连接的组件内工作。

如果先遇到指向自身的顶点,则不应该标记它,而是跳过。

使用集合并集和顶点/边计数的替代解决方案

由于树的边数比顶点数少一个,因此有另一种方法来考虑这个问题——确定 (1) 连接的组件和 (2) 比较边和顶点计算每个组件。

在许多语言中,您都有一个 Set 数据结构,它具有随时可用的接近恒定时间的 Union/Find 方法。在这种情况下,解决方案既简单又快速 - 边数接近线性。

为表示其连接组件的每个顶点创建一个集合。然后处理您的边缘列表。对于每条边,合并由两个顶点表示的集合。随着您的进行,请跟踪每个集合中的顶点数和边数。同样的例子:

初始集

Vertex         1  2  3  4  5
Belongs to     S1 S2 S3 S4 S5

Set            S1 S2 S3 S4 S5
Has # vertices 1  1  1  1  1
And # edges    0  0  0  0  0

从1到2处理边

Vertex         1  2  3  4  5
Belongs to     S1 S1 S3 S4 S5

Set            S1 S3 S4 S5
Has # vertices 2  1  1  1
And # edges    1  0  0  0

处理边缘从 2 到 3

Vertex         1  2  3  4  5
Belongs to     S1 S1 S1 S4 S5


Set            S1 S4 S5
Has # vertices 3  1  1
And # edges    2  0  0

处理边缘从 3 到 4

Vertex         1  2  3  4  5
Belongs to     S1 S1 S1 S1 S5

Set            S1 S5
Has # vertices 4  1
And # edges    3  0

处理边缘从 4 到 1

Vertex         1  2  3  4  5
Belongs to     S1 S1 S1 S1 S5

Set            S1 S5
Has # vertices 4  1
And # edges    4  0

我们可以到此为止,因为此时 S1 违反了树的顶点与边数。 S1 中有一个循环。顶点 5 指向自己还是指向其他人都没有关系。

为了后代,这是 中的一个实现.已经有一段时间了,所以请原谅我的草率。它不是最快的,但它确实在时限内通过了所有测试。不相交集编码直接来自 Wikipedia's pseudocode .

#include <stdio.h>

struct ds_node
{
    struct ds_node *parent;
    int rank;
};

struct ds_node v[25001];

void ds_makeSet(struct ds_node *x)
{
    x->parent = x;
    x->rank = 0;
}

struct ds_node* ds_find(struct ds_node *x)
{
    if (x->parent != x) x->parent = ds_find(x->parent);
    return x->parent;
}

int ds_union(struct ds_node *x, struct ds_node *y)
{
    struct ds_node * xRoot;
    struct ds_node * yRoot;

    xRoot = ds_find(x);
    yRoot = ds_find(y);

    if (xRoot == yRoot) return 0;

    if (xRoot->rank < yRoot->rank) 
    {
        xRoot->parent = yRoot;
    }
    else if (xRoot->rank > yRoot->rank) 
    {
        yRoot->parent = xRoot;
    }
    else 
    {
        yRoot->parent = xRoot;
        xRoot->rank++;
    }
    return 1;
}

int test(int n)
{
    int i, e, z = 0;

    for(i=1;i<=n;i++)
    {
        ds_makeSet(&v[i]);
    }
    for(i=1;i<=n;i++)
    {
        scanf("%d",&e);
        if (e)
        {
            if ( !ds_union(&v[i],&v[e]) ) 
            {
                for(i++;i<=n;i++) scanf("%d",&e);
                return 0;
            }
        }
        else
        {
            z++;
        }
    }
    return (z == 1);
}
int main()
{
    int runs; int n;

    scanf("%d", &runs);
    while(runs--)
    {
        scanf("%d", &n); 
        getc(stdin);

        test(n) ? puts("YES") : puts("NO");
    }
}

关于algorithm - 为什么 DFS 在检查图是否为树时速度不够快,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13253589/

相关文章:

c - 关于如何找到根据给定条件标记给定数组的所有元素的最少步数的任何提示?

c - C 中的自然排序 - "array of strings, containing numbers and letters"

c - 系统小程序 : Assertion failed - How can I solve?

python - 使用networkx从距离矩阵生成图: inconsistency - Python

java - 邻接表添加关系

javascript - Javascript中的搜索树算法,存储了所有可能的路线?

algorithm - 了解 Freeverb 的梳状滤波器实现

c - 使用 C 中的表达式树计算后缀表达式

r - 在 R 中的随机森林中提取树的每个最终节点的类分布

java - 高效的Java列表合并算法