我试图解决这个问题 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 指向自己还是指向其他人都没有关系。
为了后代,这是 c 中的一个实现.已经有一段时间了,所以请原谅我的草率。它不是最快的,但它确实在时限内通过了所有测试。不相交集编码直接来自 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/