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。
如果有多个连接组件,则移动将停止
因为一个顶点指向一个已经标记的顶点,在这种情况下,我们只是因为找到一个循环而停止
因为顶点不指向任何人(而是指向自己),在这种情况下,我们需要找到下一个未标记的顶点,然后从那里重新开始另一个df
在这个问题中,由于每个顶点最多指向另一个顶点,所以不必担心回溯的记帐问题也不必担心哪个dfs做了哪些标记,因为每个dfs只在其连接的组件中工作。
如果首先遇到指向自身的顶点,则不应标记该顶点,而应跳过该顶点。
使用集合并集和顶点/边计数的替代解决方案
由于树具有边数小于顶点数的特性,所以有另一种方法来考虑这个问题——确定(1)连接的组件和(2)比较每个组件中的边数和顶点数。
在许多语言中,您都有一个集合数据结构,它具有几乎恒定的时间联合/查找方法在这种情况下,解是容易和快速的-在边的数目接近线性。
为表示其连接组件的每个顶点创建一个集。然后处理边缘列表。对于每条边,合并由两个顶点表示的集。在执行此操作时,请跟踪每个集中的顶点数和边数。同样的例子:
初始集

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 - O(n) 中各点的绝对距离

algorithm - 包含n个节点的最优图路径

bash - 如何为bash单词扩展生成字符串?

c# - 给定一个网格,从中心开始螺旋向外,以及一个位置,ID 是什么?

algorithm - 如何正式解释一些操作?

python - 水平绘制具有层次结构的 networkx 图并操纵箭头的长度

c++ - N元树的二进制表示

java - 通过仅存储根对象在db4o中存储树

algorithm - 将来自“x”组植物的元素平均分配到“y”篮中

寻找城市所连接的最大陆地的算法​​?