CF 2044G1 - Medium Demon Problem (easy version)

Each spider chooses exactly one recipient. We can view this as a directed graph where every vertex has out-degree exactly one. Initially every spider owns one plushie. During a year, every spider that currently has a plushie sends one plushie along its outgoing edge.

codeforcescompetitive-programmingdfs-and-similargraph-matchingsgraphsimplementationtrees

CF 2044G1 - Medium Demon Problem (easy version)

Rating: 1700
Tags: dfs and similar, graph matchings, graphs, implementation, trees
Solve time: 2m 24s
Verified: yes

Solution

Problem Understanding

Each spider chooses exactly one recipient. We can view this as a directed graph where every vertex has out-degree exactly one. Initially every spider owns one plushie.

During a year, every spider that currently has a plushie sends one plushie along its outgoing edge. All transfers happen simultaneously. After receiving plushies, a spider is only allowed to keep at most one. If several plushies arrive, one survives and the rest are discarded.

Because a spider either has a plushie or does not, the state of the system is simply a binary array. Let a vertex be active if it currently owns a plushie. After one year, a vertex is active if at least one active predecessor pointed to it.

The task is to find the first year whose state is identical to the previous year's state.

The graph structure is very special. Since every vertex has exactly one outgoing edge, every connected component consists of a directed cycle with directed trees feeding into that cycle. This observation is the key to the entire problem.

The total number of vertices across all test cases is at most $2 \cdot 10^5$. Any algorithm that repeatedly simulates years can easily become quadratic. A solution around $O(n)$ per test case is required. Graph traversals such as DFS, cycle detection, and distance computations are easily fast enough.

Several edge cases are easy to misunderstand.

Consider a pure cycle:

1 -> 2 -> 3 -> 1

Every vertex always has exactly one plushie. The state never changes. Since year 1 cannot be stable by definition, the answer is 2.

Input:

1
3
2 3 1

Output:

2

A simulation that starts checking stability immediately at year 1 would incorrectly output 1.

Now consider a chain feeding a cycle:

3 -> 2 -> 1 <-> 4

Initially all vertices are active. After enough years, only the cycle vertices remain active. The stabilization time depends on how far the deepest tree vertex is from the cycle.

Input:

1
4
4 1 2 1

The answer is not the cycle length. It is determined by the maximum distance from a tree vertex to the cycle.

Another common mistake is assuming that every active vertex survives forever. A leaf with no incoming edges disappears after one step and can never return.

For example:

1
3
2 1 2

States evolve as:

111
110
110

The answer is 3.

A solution that only analyzes cycles and ignores trees would miss this behavior.

Approaches

The most direct approach is simulation.

Represent the current active set as a binary array. For each year, send one plushie from every active vertex to its recipient. Mark a vertex active next year if it receives at least one plushie. Compare consecutive states and stop once they become equal.

This is correct because it follows the process definition exactly.

The problem is that stabilization can take many years. Even though the easy version stabilizes quickly enough that simulation might appear tempting, the graph can contain long chains. In the worst case we may perform $O(n)$ transitions, each requiring $O(n)$ work, leading to $O(n^2)$ operations.

To do better, we need to understand what the process is actually doing.

Let $S_t$ be the set of active vertices at year $t$. A vertex belongs to $S_{t+1}$ if at least one predecessor belongs to $S_t$.

Initially every vertex is active.

A vertex survives for $k$ years exactly when there exists a directed path of length $k$ ending at that vertex. In a functional graph, every sufficiently long path eventually reaches a cycle. Vertices on cycles always survive. Tree vertices eventually disappear because once activity retreats toward the cycle, there is no way to regenerate it farther away.

After all tree vertices vanish, only cycle vertices remain active. From that point onward, the state never changes.

This means the stabilization year is determined solely by the deepest tree attached to any cycle.

Suppose a vertex is at distance $d$ from its cycle, measured by following outgoing edges until reaching the cycle. Such a vertex survives through year $d+1$ and disappears afterward. The last change happens when the maximum-distance vertex disappears.

If the maximum distance is $D$, then:

year 1 : initial state
year D+1 : deepest vertices still present
year D+2 : they disappear
year D+3 : state repeats

The answer becomes:

$$D + 2$$

For a graph consisting only of cycles, $D = 0$, giving answer $2$, exactly as required.

So the problem reduces to finding the maximum distance from any vertex to the cycle in its component.

Approach Time Complexity Space Complexity Verdict
Brute Force Simulation $O(n^2)$ $O(n)$ Too slow
Functional Graph Analysis $O(n)$ $O(n)$ Accepted

Algorithm Walkthrough

  1. Build the functional graph from the recipient array.
  2. Compute the indegree of every vertex.
  3. Use Kahn's algorithm on indegree-zero vertices.

Every removed vertex is outside all cycles. After repeatedly removing indegree-zero vertices, exactly the cycle vertices remain. 4. Mark all remaining vertices as cycle vertices.

In a functional graph, Kahn's process removes every tree vertex and leaves every cycle vertex. 5. Initialize distance zero for all cycle vertices. 6. Traverse the removed vertices in reverse Kahn order.

When a vertex points to a successor whose distance is already known, set:

$$dist[v] = dist[next[v]] + 1$$

This computes the number of edges from the vertex to its cycle. 7. Find the maximum distance $D$ among all vertices. 8. Output $D + 2$.

If the graph contains only cycles then $D=0$, giving answer 2.

Why it works

Kahn's algorithm removes exactly the vertices not belonging to directed cycles. Every removed vertex eventually reaches a cycle, and processing removals in reverse order guarantees that a vertex's successor distance has already been computed.

The computed value $dist[v]$ is precisely the number of steps needed to reach a cycle by following outgoing edges.

A vertex at distance $d$ remains active through year $d+1$, because there exists a path of length $d$ from that vertex to a cycle. After year $d+1$, activity can no longer reach it. The final state change occurs when the largest-distance vertices disappear. If $D$ is the maximum distance, that disappearance happens between years $D+1$ and $D+2$, so the first repeated state is year $D+2$.

Since every vertex either belongs to a cycle or has a unique path to one, the maximum distance completely determines the stabilization time.

Python Solution

import sys
from collections import deque

input = sys.stdin.readline

def solve():
    t = int(input())
    ans = []

    for _ in range(t):
        n = int(input())
        r = [x - 1 for x in map(int, input().split())]

        indeg = [0] * n
        for v in r:
            indeg[v] += 1

        q = deque()
        for i in range(n):
            if indeg[i] == 0:
                q.append(i)

        order = []

        while q:
            v = q.popleft()
            order.append(v)

            to = r[v]
            indeg[to] -= 1
            if indeg[to] == 0:
                q.append(to)

        dist = [0] * n

        for v in reversed(order):
            dist[v] = dist[r[v]] + 1

        max_dist = max(dist)
        ans.append(str(max_dist + 2))

    sys.stdout.write("\n".join(ans))

if __name__ == "__main__":
    solve()

The indegree computation prepares Kahn's algorithm. Every vertex removed by Kahn belongs to a tree leading into some cycle.

The array order stores the removal sequence. Processing it in reverse is the critical implementation detail. When a vertex is processed backward, its successor is already closer to a cycle, so its distance is known.

Cycle vertices never appear in order, so their distance naturally remains zero. This avoids any special handling for individual cycles.

The final answer is max_dist + 2. The extra two years come from the problem's year numbering. Distance zero corresponds to a graph already stable after the first exchange, whose answer is 2 rather than 0 or 1.

Worked Examples

Example 1

Input:

5
2 1 4 2 3

Graph:

1 <-> 2
5 -> 3 -> 4 -> 2
Vertex Distance to cycle
1 0
2 0
4 1
3 2
5 3

Thus:

Quantity Value
Maximum distance D 3
Answer 3 + 2 = 5

Output:

5

This example shows a long chain feeding a cycle. The deepest vertex determines the stabilization time.

Example 2

Input:

5
2 3 4 5 1

The graph is one directed cycle.

Vertex Distance to cycle
1 0
2 0
3 0
4 0
5 0
Quantity Value
Maximum distance D 0
Answer 2

Output:

2

This confirms the special case where the initial state already repeats after the first exchange.

Complexity Analysis

Measure Complexity Explanation
Time $O(n)$ Each vertex enters and leaves Kahn's queue at most once
Space $O(n)$ Indegree, distance, and removal-order arrays

The sum of all $n$ values is at most $2 \cdot 10^5$. Linear processing over all vertices is easily within the 2-second limit, and the memory usage remains comfortably below the 256 MB limit.

Test Cases

# helper: run solution on input string, return output string
import sys
import io
from collections import deque

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)

    input = sys.stdin.readline
    t = int(input())
    out = []

    for _ in range(t):
        n = int(input())
        r = [x - 1 for x in map(int, input().split())]

        indeg = [0] * n
        for v in r:
            indeg[v] += 1

        q = deque(i for i in range(n) if indeg[i] == 0)
        order = []

        while q:
            v = q.popleft()
            order.append(v)

            to = r[v]
            indeg[to] -= 1
            if indeg[to] == 0:
                q.append(to)

        dist = [0] * n
        for v in reversed(order):
            dist[v] = dist[r[v]] + 1

        out.append(str(max(dist) + 2))

    return "\n".join(out)

# provided sample
assert run(
"""5
2
2 1
5
2 3 4 5 1
5
2 1 4 2 3
5
4 1 1 5 4
10
4 3 9 1 6 7 9 10 10 3
"""
) == """2
2
5
4
5"""

# minimum size
assert run(
"""1
2
2 1
"""
) == "2"

# chain of length 2 into a 2-cycle
assert run(
"""1
4
2 1 2 3
"""
) == "4"

# pure cycle length 5
assert run(
"""1
5
2 3 4 5 1
"""
) == "2"

# long tail into cycle
assert run(
"""1
6
2 1 1 3 4 5
"""
) == "6"
Test input Expected output What it validates
2-node cycle 2 Smallest legal graph
Tail length 2 into cycle 4 Correct distance counting
Pure cycle 2 No tree vertices present
Long tail into cycle 6 Deepest vertex determines answer

Edge Cases

Consider the smallest possible graph:

1
2
2 1

Both vertices form a cycle. Kahn's algorithm removes nothing, so every distance remains zero. The maximum distance is zero, producing answer $0+2=2$. The state is unchanged after the first exchange, and year 2 is the first stable year.

Consider a long chain:

1
5
2 1 2 3 4

The graph contains cycle $1 \leftrightarrow 2$ and chain $5 \to 4 \to 3 \to 2$.

Kahn removes vertices in order:

5, 4, 3

Processing backward gives:

dist[3] = 1
dist[4] = 2
dist[5] = 3

The maximum distance is 3, so the answer is 5. The deepest vertex is exactly what controls stabilization.

Finally, consider multiple components:

1
6
2 1 4 3 4 5

There are two cycles:

1 <-> 2
3 <-> 4

and a chain:

6 -> 5 -> 4

Distances are:

1,2,3,4 : 0
5 : 1
6 : 2

The maximum distance is 2, so the answer is 4. The algorithm naturally handles all components simultaneously because Kahn's algorithm and the reverse-distance computation are global over the entire functional graph.