我认为以下方法在技术上实现了O(N+Q)
的时间复杂度。
观察
子图:图形不一定是连续的。所有图形都包含一个或多个不相交的完整连续子图,意味着:
- 没有节点在子图之间共享("不相交")
- 子图中的所有节点都连接在一起("连续")
- 没有路径连接不同的子图("完整")
我将在此后称这些图形为图的子图或只是"子图"。这些子图具有以下附加属性,这些属性是它们的定义(上面)和图形中的节点类型(它们都是具有一个外向边/指针的"父指针节点")的结果:
- 所有这样的子图必须有一个循环(因为循环是它们终止或关闭的唯一方式)
- 循环可以是任意长度
cycle.Len >= 1
- 此外,可能有任意数量的树(
t >= 0
)附加到其根(底部)的循环上
- 所有节点都在循环中或在这些树之一中(树的根位于循环中,但也计算为树的一部分)
术语:
- 循环长度:循环中节点的数量。
- 循环基准:在循环中选择的任意节点,用于测量两个节点之间的距离,无论这两个节点是在同一个循环中还是在同一个子图中。
- 树基准:附加到循环上的树的基础节点或根节点。由于树基准也是将其连接到循环的节点,因此树基准节点被计算为在循环中(并且也是其树的一部分)。
- 距离:对于循环中的节点,这是从该节点到循环基准的距离(跳数)(如果它是循环基准则为0)。对于树中的节点(不包括树基准节点,树基准节点算作在循环中),这是从该节点到树基准节点的距离。
碰撞情况
微不足道
在图中可能有许多种碰撞方式或"形式",但我们可以预先识别出两种微不足道的情况:
(A, B) 关系 |
是否碰撞? |
碰撞距离 |
相同节点 |
是 |
0 |
不同的子图 |
否 |
-1 |
显然,如果A和B是同一个节点,则它们相撞的距离为零。同样,如果它们位于两个不同的子图中,则它们永远不会相撞,因为子图之间没有连接。对于接下来的碰撞情况,我将假定这两种情况已经被过滤,以便:
1. A和B被认为是不同的节点,且
2. A和B被认为在同一个子图中
非平凡关系:
下表涵盖了两个节点之间所有其他的、非平凡的关系。
(A, B) 关系 | 是否相撞? | 碰撞距离 | 备注
-|-|-|-
在同一圈中 | 否 | -1 | 圈中的节点始终保持相同的距离
A在树中,B在环中(或反之) | 如果它们同时到达A的treeBase | -1 或者 A.treeDist | 如果 B.cycleDist = (A.treeDist MOD cycle.Len)
A和B在不同的树中 | 如果A和B到其cycle.Base的距离等于MOD cycle.Len | MAX(A.treeDist, B.treeDist) | 当更远的节点到达环(树根)时,它们相遇
A和B在同一棵树中,但有不同的treeDist | 如果它们的treeDist取模后相等 | MAX(A.treeDist, B.treeDist) | 当更远的节点到达环(树根/基)时,它们相遇
A和B在同一颗树上,并且treeDist相等 | 是 | 在它们在树中的最低共同祖先(LCA)处 | 必须向树上查询
以上几次应用了一个重要原则,即
圈中两个不同的节点永远不会相撞。这是因为当每个节点沿着其路径绕着圈走时,它们总是保持相同的距离,没有一种方法可以让一个节点的路径在圈中"追上"另一个节点的路径。只有
如果它们从圈中的同一个节点开始,它们才能相撞。
这意味着:
- 一个环中的两个不同节点永远不会相撞。
- 一棵树中的节点只能与一个在环中的节点相撞,如果它们到环基点的距离之和对于循环长度取模后相同(也就是除以循环长度的余数相同)。
- 对于两个不同树的节点和同一棵树但距离树基点不同的两个节点,这也是正确的。
- 在所有这些情况(来自#2和#3)中,当最远离其树基点的节点到达循环时(也是其树基点),它们将相撞。 这是因为环中的节点无法“追赶”对方,因此一旦它们同时进入环中,它们必须始终保持相同。 因此,当更远的节点最终到达循环基点时,它们总是会相撞。
另一个重要的结果是,表格中所有情况都可以用O(1)
时间回答,除了最后一个,只需用以下简单确定的信息注释节点即可:
- 它们的基础节点(树或循环)
- 它们到该基础节点的距离
- 它们所属的子图
- 它们所在子图的循环长度
当初始化图时,这些都可以在每个节点O(1)
或总时间O(N)
内轻松确定。
方法
节点
在节点最初加载到图中(MPDGraph对象)后,我用上面列出的其他信息注释节点。该过程(称为代码中的“映射”)如下进行:
- 选择任何一个节点
- 沿着它的路径一直走,直到到达了已经在它的路径上的节点或已经被映射过的节点
- 如果#2穿过了自己的路径,则我们找到了一个新的循环。将我们穿过的节点指定为循环的基点,并填充映射属性(cycle, 基点节点, 距离等)。逐步解开我们的路径,每次向上返回并标记其为InCycle,直到我们再次到达基本节点。此时,我们位于我们的路径进入环形的树的底部,因此当我们返回路径中的上一个节点时,我们将转而将其标记为树节点,直到返回我们路径中的第一个节点。
- 如果相反,#2达到了已映射的节点,则我们将把路径附加到该节点并复制其树/循环、基点等信息到我们当前的节点。然后,像#3一样返回我们的路径,设置每个节点的映射属性。
- 如果有任何未映射的节点,请选择一个并转到#2。
这需要O(N)
时间。
查询
我们有一个方法(称为MPDGraph.FindCollision),给定两个节点,将应用上面的两个碰撞案例表中的规则并返回结果。 对于除最后一个情况(在同一树上且距离相同的节点)之外的每种情况,都可以通过使用映射属性在O(1)时间内确定距离。
如果两个节点在同一颗树中,且距离基准节点相同,则它们可以在它们之间和共同的treeBase节点之间的任何地方相遇。 对于这种情况,FindCollision(A,B)方法调用findTreeDistance(A,B)方法:
1. 如果它们是同一节点,则返回零。
2. 否则,它会检查以前计算过的距离的高速缓存,查看是否已经为这两个节点计算了距离。 如果是,则返回该值。
3. 否则,它调用findTreeDistance,传入当前两个节点的父节点以获取它们之间的距离,并加上1。 然后将其添加到缓存中并返回该值。
没有这种记忆化(即缓存),每次查询此类型平均需要约O(log N)。 带有缓存时很难计算,但我猜不会更差于O(log log N),但对于Q远大于N的情况,这将收敛到O(1)。
这使得查询处理时间复杂度在O(Q log log N)和O(Q)之间,总时间在O(N + Q(log log N))和O(N + Q)之间。
代码
public static int[] collisionTime(int N, int Q, int[] A, int[,] queries)
{
var graph = new MPDGraph(A);
graph.MapAllNodes();
int[] answers = new int[queries.GetLength(0)];
for (int i = 0; i < answers.Length; i++)
{
answers[i] = graph.FindCollision(queries[i, 0], queries[i, 1]);
}
return answers;
}
这里使用了以下类:
MPDGraph 类:
class MPDGraph
{
public Node[] Nodes;
Dictionary<(Node, Node), int> cachedDistances = new Dictionary<(Node, Node), int>();
public MPDGraph(int[] Pointers)
{
Nodes = new Node[Pointers.Length];
for (int i = 0; i < Nodes.Length; i++) { Nodes[i] = new Node(i); }
for(int i = 0; i < Nodes.Length; i++) { Nodes[i].toNode = Nodes[Pointers[i]]; }
}
public void MapAllNodes()
{
for(int i=0; i<Nodes.Length; i++)
{
if (!Nodes[i].isMapped)
MapPath(Nodes[i], 1);
}
}
public Boolean MapPath(Node curr, int pathNo)
{
Boolean inCycle = false;
curr.pathNo = pathNo;
Node next = curr.toNode;
if (next.IsInPath)
{
Cycle Cycle = new Cycle(this, next, curr.pathNo - next.pathNo + 1);
curr.Map(Cycle);
return true;
}
else if (next.isMapped)
{
if (next.IsInCycle)
{
curr.Map(next.Cycle, false, next, 1);
}
else
{
curr.Map(next.Cycle, false, next.BaseNode, next.Distance + 1);
}
return false;
}
else
{
inCycle = MapPath(next, pathNo+1);
if (inCycle)
{
if (next.Cycle.Base == next || next.Distance == 0)
{
curr.Map(next.Cycle, false, next, 1);
return false;
}
else
{
curr.Map(next.Cycle);
}
}
else
{
curr.Map(next.Cycle, false, next.BaseNode, next.Distance + 1);
}
return inCycle;
}
}
public int FindCollision(int index1, int index2)
{
Node node1 = Nodes[index1];
Node node2 = Nodes[index2];
if (node1.Cycle != node2.Cycle)
return -1;
else if (node1 == node2)
return 0;
else if (node1.IsInCycle && node2.IsInCycle)
return -1;
else
{
int dist1 = node1.Distance + (node1.IsInCycle ? 0 : node1.BaseNode.Distance);
int dist2 = node2.Distance + (node2.IsInCycle ? 0 : node2.BaseNode.Distance);
int cycleLen = node1.Cycle.Length;
if ((dist1 % cycleLen) != (dist2 % cycleLen))
{
return -1;
}
else
{
if (node1.IsInCycle || node2.IsInCycle)
{
return (!node1.IsInCycle ? node1.Distance : node2.Distance);
}
else if (node1.BaseNode != node2.BaseNode)
{
return Math.Max(node1.Distance, node2.Distance);
}
else
{
if (node1.Distance != node2.Distance)
{
return Math.Max(node1.Distance, node2.Distance);
}
else
{
return findTreeDistance(node1, node2);
}
}
}
}
}
int findTreeDistance(Node node1, Node node2)
{
if (node1 == node2) return 0;
if (node1.index > node2.index)
{
var tmp = node1;
node1 = node2;
node2 = tmp;
}
int dist;
if (cachedDistances.ContainsKey((node1,node2)))
{
dist = cachedDistances[(node1, node2)];
}
else
{
dist = findTreeDistance(node1.toNode, node2.toNode) + 1;
cachedDistances.Add((node1, node2), dist);
}
return dist;
}
}
节点类:
class Node
{
public int index { get; set; }
public Node toNode { get; set; }
public Node(int Index_) { this.index = Index_; }
public Cycle Cycle;
public Boolean IsInCycle = false;
public Node BaseNode;
public int Distance = -1;
public int TotalDistance { get { return Distance + (IsInCycle ? 0 : BaseNode.Distance); } }
public int pathNo = -1;
public Boolean isMapped { get { return Cycle != null; } }
public Boolean IsInPath { get { return (pathNo >= 0); } }
public void Map(Cycle Cycle, bool InCycle = true, Node BaseNode = null, int distance_ = -1)
{
this.Cycle = Cycle;
IsInCycle = InCycle;
if (InCycle)
{
this.BaseNode = Cycle.Base;
Distance = (Cycle.Length + (Cycle.Base.pathNo - pathNo)) % Cycle.Length;
}
else
{
this.BaseNode = BaseNode;
Distance = distance_;
}
pathNo = -1;
}
}
循环类:
class Cycle
{
public MPDGraph Graph;
public Node Base;
public int Length;
public Cycle(MPDGraph graph_, Node base_, int length_)
{
Graph = graph_;
Base = base_;
Length = length_;
}
}
性能测量:
节点数 |
构建和映射图表 平均微秒数 |
问题数量 |
所有问题 平均微秒数 |
问题的平均 微秒数 |
总平均 微秒数 |
50 |
0.9 |
1225 |
26 |
0.0212 |
26.9 |
500 |
10.1 |
124750 |
2267 |
0.0182 |
2277.1 |
1000 |
23.4 |
499500 |
8720 |
0.0175 |
8743.4 |
5000 |
159.6 |
12497500 |
229000 |
0.0183 |
229159.6 |
10000 |
345.3 |
49995000 |
793212 |
0.0159 |
793557.3 |
O(N^2 + Q)
,这与O(Q*N)
没有实质性的改进。 - RBarryYoungO(N log N)
的时间,然后回答查询需要O(Q log N)
的时间。因此总时间复杂度为O((N+Q) log N)
。 - RBarryYoungO(N + Q)
的平均时间复杂度。对于任意随机结构或随机查询集,它几乎总能达到这个复杂度。然而,对于某些病态结构和非随机查询集(始终匹配,但距离最大),我还没有完全解决。 - RBarryYoung