I believe that the following approach technically achieves O(N+Q) time complexity.
Observations
Subgraphs: The graph is not necessarily contiguous. All graphs consist or one or more disjoint contiguous complete subgraphs, meaning:
- No nodes are shared between subgraphs ("disjoint")
- All of the nodes in the subgraph are connected ("contiguous")
- There are no paths connecting different subgraphs ("complete")
I will hereafter refer to these as the subgraphs of the graph or just "subgraphs". These subgraphs have the following additional properties, which are a consequence of their definition (above) and the types of nodes in the graph (they are all "parent-pointer nodes" with exactly one out-edge/pointer):
- All such subgraphs must have exactly one cycle in them (because a cycle is the only way that they can terminate or be closed)
- The cycle can be of any length
cycle.Len >= 1
- Additionally, there may be any number (
t >= 0) trees attached to the cycle at their root (base)
- All nodes are either in the cycle or in one of these trees (the roots of the trees are in the cycle, but also counted as part of a tree)
Terms:
- cycle Length: The number of nodes in a cycle.
- cycle Base: An arbitrarily chosen node in the cycle used to measure and distances between two nodes in the same cycle, and also any two nodes in the same subgraph.
- tree Base: The base or root node of one of the trees attached to the cycle. As the tree base is also the node that attaches it to the cycle, tree base nodes are counted as being in the cycle (and also part of their tree).
- Distance: For a node in the cycle, this is the distance (number of hops) from that node to the cycle Base (zero if it is the cycle Base). For a node in a tree (not counting tree Base nodes, which count as in the cycle), this is the distance from that node to the tree Base node.
Collisions Cases
Trivial
There are many ways or "forms" of collisions possible in a graph, but we can identify two trivial cases upfront:
| (A, B) Relation |
Collide? |
Collision Distance |
| same node |
Yes |
0 |
| different subgraphs |
No |
-1 |
Obviously, if A and B are the same node, then they trivially collide at distance zero. Likewise, if they are in two different subgraphs, then they can never collide because there are no connections between the subgraphs. For the collision cases that follow I will be assuming that these two cases have already been filtered out so that:
- A and B are assumed to be different nodes, and
- A and B are assumed to be in the same subgraph
Non-Trivial
The following table covers all of the other, non-trivial, cases of the relation between two nodes.
| (A, B) Relation |
Collide? |
Collision Distance |
Notes |
| same cycle |
No |
-1 |
nodes in cycle always stay the same distance apart |
| A in a tree & B in the cycle (or vice-versa) |
if they both arrive at A's treeBase at the same time |
-1 OR A.treeDist |
if B.cycleDist = (A.treeDist MOD cycle.Len) |
| A and B are in different trees |
if A and B's distance to their cycle.Base is equal MOD cycle.Len |
MAX(A.treeDist, B.treeDist) |
They meet when the farther one gets to the cycle (tree root) |
| A & B are in the same tree, but have different treeDist's |
If their treeDist's are equal MOD cycle.Len |
MAX(A.treeDist, B.treeDist) |
They meet when the farther one gets to the cycle (tree root/base) |
| A & B are in the same tree, and have the same treeDist's |
Yes |
At their lowest common ancestor (LCA) in the tree |
Have to search up the tree |
One important principle applied several times above is that two different nodes in a cycle can never collide. This is because when each node follows its path around the cycle, they will always stay the same distance apart, there is no way for one node's path to "catch-up" to another's in the cycle. They can only "collide" if they start out in the cycle at the same node.
The consequences of this are that:
- Two different nodes in the cycle can never collide.
- A node in a tree can only collide with a node in a cycle, if their total distances to the cycle base are the same Modulo the cycle length (that is the remainder when divided by the cycle length).
- This is also true for two nodes in different trees and two nodes in the same tree but with different distances to their tree base.
- In all of these cases (from #2 and #3), they will collide when the node that is farthest from its tree Base gets to the cycle (which is also its tree base). This is because nodes in the cycle cannot "catch-up" to each other, so they must always be the same once they are both in the cycle. Thus they always collide when the farther one finally gets to the cycle.
Another important consequence is that every case in both tables above, except for the last one, can be answered in O(1) time, simply by annotating the nodes with so easily determined information:
- their Base node (tree or cycle)
- their Distance to that base node
- the Subgraph they belong to
- the Length of their subgraph's Cycle
These can all be easily determined when initializing the graph in O(1) time per node (or O(N) total time).
Approach
Nodes
After the nodes are initially loaded into the graph (MPDGraph object), then I annotate the nodes with the additional information listed above. This process (called "Mapping" in the code) proceeds as follows:
- Pick any node
- Follow it's path until it "terminates" by reaching a node already in it's path, or a node that was previously mapped
- If #2 crossed it's own path, then we've found a new cycle. Designate the node we crossed as the base node of the cycle, and fill-in the mapping properties (cycle, base node, distance, etc.). Unwind our path one node at a time, filling in each node and marking it as InCycle as we go back up the path until we reach the base node again. Now we are ate the base of the tree that our path followed into the cycle, so when we move back to the pervious node in the path we switch to marking it as a tree node, until we return to the first node in our path.
- If instead, #2 reached an already mapped node, then we well attach our path to that node and copy its tree/cycle, base etc. information to our current node. Then we will return back up our path as in #3, setting the mapping properties of each node as we go,
- If there are any unmapped nodes, pick one and goto #2.
This all takes O(N) time.
Queries
We have a method (called MPDGraph.FindCollision) that given two nodes will apply the rules in the two Collision Cases tables above and return the result. For very case except the last (nodes in same tree and same distance) the distance can be determined in O(1) time by using the mapping properties.
If the two nodes are in the same tree and are also the same distance from their tree base, then they could meet anywhere between them and their common treeBase node. For this case the FindCollision(A,B) method calls the findTreeDistance(A,B) which:
- Returns zero if they are the same node.
- Otherwise it checks a cache of previously calculated distances to see if it has already been calculated for these two node. If so, then it returns that value.
- Otherwise, it calls
findTreeDistance passing in the parents of the current two nodes to get their distance, and adds one to that. Then it adds this to the cache and returns the value.
Without this memoization (i.e., the cache) this would take on average apprx. O(log N) for each query of this type. With the memoization it is hard to calculate but I would guess no worse than O(log log N) but for Q counts much larger than N, this will converge to O(1).
This makes the query processing time complexity somewhere between O(Q log log N) and O(Q), and the total time between O(N + Q(log log N)) and O(N + Q).
Code
public static int[] collisionTime(int N, int Q, int[] A, int[,] queries)
{
// create the graph and fill-in the mapping attributes for all nodes
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;
}
This utilizes the following classes,
MPDGraph Class:
// MPDG: Mono-Pointing, Directed Graph
// An MPDG is a directed graph where every node has exactly one out-edge.
// (MPDG is my own term, I don't know the real name for these)
class MPDGraph
{
public Node[] Nodes;
Dictionary<(Node, Node), int> cachedDistances = new Dictionary<(Node, Node), int>();
// constructor
public MPDGraph(int[] Pointers)
{
Nodes = new Node[Pointers.Length];
// first fill the array with objects
for (int i = 0; i < Nodes.Length; i++) { Nodes[i] = new Node(i); }
// apply their pointers
for(int i = 0; i < Nodes.Length; i++) { Nodes[i].toNode = Nodes[Pointers[i]]; }
}
// map all of the nodes by filling their mapping properties
public void MapAllNodes()
{
for(int i=0; i<Nodes.Length; i++)
{
if (!Nodes[i].isMapped)
MapPath(Nodes[i], 1);
}
}
// recursively map a path of unmapped nodes, starting from curr
// returns true if curr is in a cycle, false otherwise
public Boolean MapPath(Node curr, int pathNo)
{
Boolean inCycle = false;
curr.pathNo = pathNo;
Node next = curr.toNode;
if (next.IsInPath)
{
// we have found a new cycle
Cycle Cycle = new Cycle(this, next, curr.pathNo - next.pathNo + 1);
curr.Map(Cycle);
return true;
}
else if (next.isMapped)
{
// we are joining an already partially mapped tree
if (next.IsInCycle)
{
// next is a tree-Base, the top of our tree and also in the cycle
curr.Map(next.Cycle, false, next, 1);
}
else
{
// next is a normal tree-node
curr.Map(next.Cycle, false, next.BaseNode, next.Distance + 1);
}
return false;
}
else
{
// continue forward on the path, recurse to the next node
inCycle = MapPath(next, pathNo+1);
if (inCycle)
{
if (next.Cycle.Base == next || next.Distance == 0)
{
//we have returned from the cycleBase, which is also a treeBase
// so, switch from Cycle to Tree
curr.Map(next.Cycle, false, next, 1);
return false;
}
else
{
// still in the cycle
curr.Map(next.Cycle);
}
}
else
{
//returned in tree
curr.Map(next.Cycle, false, next.BaseNode, next.Distance + 1);
}
return inCycle;
}
}
// Given two starting nodes, determine how many steps it takes until their
// paths collide. Returns -1 if they will never collide.
public int FindCollision(int index1, int index2)
{
Node node1 = Nodes[index1];
Node node2 = Nodes[index2];
// eliminate trivial cases
if (node1.Cycle != node2.Cycle)
return -1; // cant collide if they're in different subgraphs
else if (node1 == node2)
return 0; // if they're the same node, then distance = 0
else if (node1.IsInCycle && node2.IsInCycle)
return -1; // different nodes in a cycle never collide
else
{ // they're both in the same subgraph, use math to tell if they collide
// get their distances to the cycle base
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;
// use math: modulo(cycle length)
if ((dist1 % cycleLen) != (dist2 % cycleLen))
{
return -1; // incompatible distances: cannot possibly collide
}
else
{
// they must collide somewhere, figure out how far that is
if (node1.IsInCycle || node2.IsInCycle)
{
// if one is in the cycle, they will collide when
// the other one reaches the cycle (it's treeBase)
return (!node1.IsInCycle ? node1.Distance : node2.Distance);
}
else if (node1.BaseNode != node2.BaseNode)
{
// They are in different trees: they will collide at
// the treeBase of the node that is farther
return Math.Max(node1.Distance, node2.Distance);
}
else
{
// They are in the same tree:
if (node1.Distance != node2.Distance)
{
//if they are in the same tree, but have different distances
// to the treeBase, then they will collide at the treeBase
// when the farther one arrives at the treeBase
return Math.Max(node1.Distance, node2.Distance);
}
else
{
// the hard case, have to walk down their paths
// to find their LCA (Lowest Common Ancestor)
return findTreeDistance(node1, node2);
}
}
}
}
}
int findTreeDistance(Node node1, Node node2)
{
if (node1 == node2) return 0;
// normalize their order
if (node1.index > node2.index)
{
var tmp = node1;
node1 = node2;
node2 = tmp;
}
// check the cache
int dist;
if (cachedDistances.ContainsKey((node1,node2)))
{
dist = cachedDistances[(node1, node2)];
}
else
{
// keep recursing to find where they meet
dist = findTreeDistance(node1.toNode, node2.toNode) + 1;
// cache this new distance
cachedDistances.Add((node1, node2), dist);
}
return dist;
}
}
Node Class:
// Represents a node in the MPDG (Mono-Pointing Directed Graph) with the constraint
// that all nodes have exactly one out-edge ("toNode").
class Node
{
// Primary properties (from input)
public int index { get; set; } // this node's unique index (to the original array)
public Node toNode { get; set; } // what our single out-edge is pointing to
public Node(int Index_) { this.index = Index_; }
// Mapping properties
// (these must be filled-in to finish mapping the node)
// The unique cycle of this node's subgraph (all MPDG-subgraphs have exactly one)
public Cycle Cycle;
// Every node is either in their subgraphs cycle or in one of the inverted
// trees whose apex (base) is attached to it. Only valid when BaseNode is set.
// (tree base nodes are counted as being in the cycle)
public Boolean IsInCycle = false;
// The base node of the tree or cycle that this node is in.
// If (IsInCycle) then it points to this cycle's base node (cycleBase)
// Else it points to base node of this node's tree (treeBase)
public Node BaseNode;
// The distance (hops) from this node to the BaseNode
public int Distance = -1; // -1 if not yet mapped
// Total distance from this node to the cycleBase
public int TotalDistance { get { return Distance + (IsInCycle ? 0 : BaseNode.Distance); } }
// housekeeping for mapping nodes
public int pathNo = -1; // order in our working path
// Derived (implicit) properties
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; // clean-up the path once we're done
}
}
Cycle Class:
// represents the cycle of a unique MPDG-subgraph
// (should have one of these for each subgraph)
class Cycle
{
public MPDGraph Graph; // the MPDG that contains this cycle
public Node Base; // the base node of a subgraph's cycle
public int Length; // the length of this cycle
public Cycle(MPDGraph graph_, Node base_, int length_)
{
Graph = graph_;
Base = base_;
Length = length_;
}
}
Performance Measurements:
| Node Count |
Build & Map Graph
mean microsecs |
Question Count |
All Questions
mean microsecs |
Question mean
microseconds |
Total mean
microseconds |
| 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 |
