1

この問題を解決しようとしました 問題の説明 与えられたグラフにサイクルがあるかどうか（ツリーであるかどうか）を確認するのが正しい考えのようです。しかし、私のコードはテスト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.
4

1 に答える 1

2

パスカルについてはほとんど何も知らないので、あなたがしていることを誤解している可能性がありますが、主な原因は、fin訪問した頂点のマークを外したところにあると思います。これにより、各頂点からDFSを実行する必要がありますが、コンポーネントごとに1つだけ実行する必要があります。

複数のコンポーネントが接続されている場合、移動は停止します

  • 頂点はすでにマークされている頂点を指しているため、この場合、サイクルが見つかったために停止します。
  • 頂点は誰も（それ自体ではなく）指しているため、この場合、次のマークされていない頂点を見つけて、そこから別のDFSを再開する必要があります。

この問題では、各頂点がほとんどの場合、他の1つの頂点を指しているため、バックトラックの簿記について心配する必要はありません。また、それぞれが接続されたコンポーネント内でのみ機能するため、どのDFSがどのマーキングを実行したかを心配する必要はありません。

それ自体を指す頂点が最初に検出された場合、それはまだマークされていないはずですが、スキップされます。

SetUnionとVertex/EdgeCountを使用した代替ソリューション

ツリーには、エッジの数が頂点の数より1つ少ないという特性があるため、問題について考える別の方法があります。（1）連結成分を決定し、（2）それぞれのエッジと頂点の数を比較します。成分。

多くの言語では、ほぼ一定の時間のUnion/Findメソッドをすぐに利用できるSetデータ構造があります。この場合、解決策は簡単で高速です。エッジの数はほぼ線形です。

接続されたコンポーネントを表す頂点ごとにセットを作成します。次に、エッジリストを処理します。エッジごとに、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がそれ自体を指しているのか、他の誰かを指しているのかは関係ありません。

後世のために、ここにの実装があります。久しぶりですので、だらしのないことはご容赦ください。最速ではありませんが、制限時間内にすべてのテストに合格します。互いに素な集合のコーディングは、ウィキペディアの擬似コードから直接引用されています。

#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");
    }
}
于 2012-11-06T17:24:32.177 に答える