Functional Graphs¶

In one sentence

If every node has exactly one outgoing edge, then walking from any node must end up going round a cycle forever. So the graph is a set of cycles with chains hanging off them, and one while loop with a visited list handles it in \(O(n)\).

Where we are

From the lesson of 11 Oct 2026 (Set 13). We drew the shape, then solved Badge and both versions of Books Exchange in class, and worked out the idea of 2033E. Everything so far is the permutation case (cycles only). On 18 Oct we did F (still a permutation) and then graphs with tails: G with three states (§7), and H, H2, I by peeling the tails (Topological Sorting §3).

1. What problem does it solve?¶

Example — 1020B · Badge (13 · A, rating 1000)

There are \(n\) students. When the teacher catches student \(i\), that student blames student \(p_i\). The teacher starts with student \(a\), puts a hole in their badge, goes to the student they blame, puts a hole in that badge, and so on. The teacher stops at the first student who already has a hole.

For every starting student \(a\) from \(1\) to \(n\), print the student who ends up with two holes.

Limits: \(n \le 1000\).

Input      Output
3
2 3 2      2 2 3

The input is one list: for every \(i\), a single number \(p_i\). Read it as "from \(i\) there is one edge, and it goes to \(p_i\)". A lot of problems hide this graph behind a story: blames, gives the book to, runs to, is afraid of. As soon as each \(i\) comes with exactly one \(p_i\), draw the graph.

For the sample:

graph LR
  1 --> 2
  2 --> 3
  3 --> 2

Start at 1: the teacher visits 1, 2, 3, then 2 again. Answer 2. Start at 3: visits 3, 2, then 3 again. Answer 3.

2. The shape¶

2.1 Degree, in-degree, out-degree¶

The degree of a node is the number of edges that touch it. It belongs to one node. (The longest path in a tree is the diameter, a different thing. See Tree Diameter.)

In a directed graph we count the two directions separately:

out-degree: edges that start at the node,
in-degree: edges that point to the node.

A functional graph is a directed graph where every node has out-degree exactly \(1\). The name comes from the fact that the edges are a function: \(i \mapsto a_i\).

2.2 The picture from class¶

i    : 1 2 3 4 5 6 7 8
a[i] : 2 3 1 5 4 4 6 7

graph LR
  1 --> 2
  2 --> 3
  3 --> 1
  8 --> 7
  7 --> 6
  6 --> 4
  4 --> 5
  5 --> 4

Three questions, and your answers from class:

Start anywhere and keep walking. What happens? "We eventually get into an infinite loop." There is always a next node, and there are only \(n\) nodes, so after at most \(n\) steps we must step on a node we have already seen. From there the walk repeats.
Once we are in a cycle, can we leave? No. Each node on the cycle has only one outgoing edge, and it is used to stay on the cycle.
Is there any rule for the in-degree? No. Count them in the picture: node 4 has in-degree \(2\), node 8 has in-degree \(0\), the rest have \(1\). In general it can be anything from \(0\) to \(n\).

So every connected part of the graph looks the same: one cycle, with chains (tails) pointing into it. Above, the first part is a cycle of length 3 with no tail, and the second is a cycle of length 2 (\(4 \rightleftarrows 5\)) with the tail \(8 \to 7 \to 6\).

2.3 Special case: permutations¶

If \(p\) is a permutation, every number appears exactly once in the list, so every node has in-degree exactly \(1\) as well. Then there are no tails:

a tail has to begin at a node that nobody points to (in-degree \(0\)), and
a tail has to join the cycle at a node that already has an edge coming in from the cycle (in-degree \(2\)).

Neither exists, so the graph is only cycles. This was your question in Books Exchange: "what if the book is never returned?" It always is, because the walk from \(i\) cannot get stuck in a cycle that does not contain \(i\).

one outgoing edge per node             ->  cycles with tails
also a permutation (one edge in, too)  ->  cycles only

2.4 Indices¶

The statement numbers the nodes \(1..n\), and a Python list starts at \(0\). Choose one of these when you read the input and never mix them:

p = [0] + [int(z) for z in input().split()]   # 1-indexed: p[i] is exactly the statement's p_i
p = [int(z) - 1 for z in input().split()]     # 0-indexed: remember the + 1 when printing

3. Template¶

Walk along the edges with a while loop, marking nodes as you go:

cur = start
while not vis[cur]:
    vis[cur] = True
    cur = p[cur]
# cur is the first node we reached twice

Use a loop here and never recursion: a cycle can have \(2 \cdot 10^5\) nodes, which is far deeper than Python's recursion limit.

The whole topic is about one decision: is vis created again for every starting node, or once for the whole graph?

`vis` is …	each start walks …	total cost	used in
reset for every start	up to \(n\) steps	\(O(n^2)\)	Badge, Books Exchange (easy)
shared by all starts	only over new nodes	\(O(n)\)	Books Exchange (hard)

4. Worked solution — Badge¶

\(n \le 1000\), and one walk takes at most \(n\) steps, so walking again from every start is \(n^2 = 10^6\) steps. That is fast enough, and it is exactly the template with a fresh vis each time.

The code from class (0-indexed, so + 1 when we store the answer):

    p = [int(z) - 1 for z in input().split()]

    ans = []
    for a in range(n):
        cur = a
        vis = [False for _ in range(n)]
        while not vis[cur]:
            vis[cur] = True
            cur = p[cur]
        ans.append(cur + 1)

    print(*ans)

5. Lesson of 11 Oct — Books Exchange¶

5.1 1249B1 · Books Exchange (easy) (13 · B, rating 1000)¶

Problem

\(n\) kids each own one book. \(p\) is a permutation. At the end of every day, kid \(i\) gives the book they are holding to kid \(p_i\). For every kid, on which day does their own book come back to them for the first time?

Limits: \(q \le 200\) queries, \(n \le 200\).

p = 5 1 2 4 3      ->      4 4 4 1 4

The book of kid 1 goes \(1 \to 5 \to 3 \to 2 \to 1\): four days. Kid 4 gives the book to themself: one day.

Follow the book and count the steps until it is back at \(i\). By §2.3 it always comes back.

    for i in range(1, n + 1):
        day = 1
        cur = p[i]
        while cur != i:
            cur = p[cur]
            day += 1
        ans.append(day)

day starts at \(1\) because the first step (cur = p[i]) has already been taken.

5.2 1249B2 · Books Exchange (hard) (13 · C, rating 1300)¶

The same problem with \(n \le 2 \cdot 10^5\) (and the sum of \(n\) over all queries \(\le 2 \cdot 10^5\), so the number of queries does not matter).

Why 5.1 is too slow. Imagine one big cycle through all \(n\) kids. Every kid walks all the way round it: \(n\) walks of \(n\) steps, \(n^2 = 4 \cdot 10^{10}\). We submitted it in class and got TLE.

What we noticed. Everybody on the same cycle has the same answer: the length of the cycle. So walk each cycle once, remember who is on it, and give all of them the answer together.

p = 4 6 2 1 5 3
cycles: {1, 4}  {2, 6, 3}  {5}
answer:  2 3 3 2 1 3

The code from class:

    vis = [False for _ in range(n + 1)]

    d = [0 for _ in range(n + 1)]
    # where do we start?
    for i in range(1, n + 1):
        if vis[i]:
            continue
        # i is in a new cycle
        # let's try to find the length
        members = [i]
        cur = p[i]
        while cur != i:
            members.append(cur)
            cur = p[cur]

        # till here
        # we have all the members for the cycle
        for member in members:
            vis[member] = True
            d[member] = len(members)

The bug we had in class

The first version checked if vis[i] but never set vis[member] = True. Nothing was ever skipped, so it was still the \(O(n^2)\) solution. A visited list only helps if you also write to it.

Is a for with a while inside \(O(n^2)\)? Not here. A node is put into members only while it is unvisited, and it is marked straight after, so over the whole run each node is walked once. The total is \(O(n)\). Count how often each line can run in total, not how deeply the loops are nested.

This loop is for permutations

while cur != i stops only when the walk returns to its start. That is guaranteed when \(p\) is a permutation. If \(i\) is on a tail, the walk enters the cycle and never sees \(i\) again: an infinite loop. With tails, walk with while not vis[cur] as in §3. Telling "I found a new cycle" apart from "I ran into an old one" needs one more idea, which is the next lesson.

5.3 List or dictionary for `vis`?¶

You asked whether a dictionary would be faster. For this problem the list is the fastest choice.

	`vis = [False] * (n + 1)`	`vis = {}`
lookup	direct index	hash the key, then look it up: also \(O(1)\), but several times slower
memory	one slot for every index from \(0\) to the largest one	one entry per key you actually store
use it when	keys are \(1..n\) and \(n\) is small enough to allocate	keys are huge or sparse, for example \(1000\) ids anywhere up to \(10^9\)

A list of \(10^9\) booleans cannot be allocated, and almost all of it would be unused. A dictionary stores only the \(1000\) keys that exist. Here the keys are \(1..n\) with \(n \le 2 \cdot 10^5\), so use the list.

6. Idea only — 2033E · Sakurako, Kosuke, and the Permutation (13 · E, rating 1400)¶

Problem

A permutation is simple if every \(i\) has \(p_i = i\) or \(p_{p_i} = i\). In one operation you swap \(p_i\) and \(p_j\) for any two positions. What is the smallest number of operations that makes \(p\) simple?

What we worked out in the last minutes of class:

\(p_i = i\) is a node pointing to itself, a cycle of length \(1\). \(p_{p_i} = i\) means going two steps brings you back, a cycle of length \(2\). So simple means every cycle has length \(\le 2\).
Swap \(p_i\) and \(p_j\) with \(i\) and \(j\) on the same cycle: the cycle splits into two.
Swap with \(i\) and \(j\) on different cycles: the two cycles merge. We never want that.
So each cycle is handled alone, and the best move is to cut off a piece of length \(2\) every time. Your examples: \(6 \to 2 + 4 \to 2 + 2 + 2\) is two operations, and \(7 \to 2 + 5 \to 2 + 2 + 3 \to 2 + 2 + 2 + 1\) is three.

A cycle of length \(L\) needs \(\lfloor (L - 1) / 2 \rfloor\) operations, and the answer is the sum over all cycles.

\(L\)	1	2	3	4	5	6	7
operations	0	0	1	1	2	2	3

Not L // 2

In class we said "divide the length by two". Be careful with the exact formula: L // 2 gives \(1\) for \(L = 2\) and \(3\) for \(L = 6\), but the table says \(0\) and \(2\). Use (L - 1) // 2.

The code is §5.2 with one line changed: add (len(members) - 1) // 2 to the answer and drop d. Note that \(n\) goes up to \(10^6\) here, so read with sys.stdin.readline and submit with PyPy 3-64.

7. Lesson of 18 Oct — F and G¶

7.1 F · 884C · Bertown Subway (rating 1500)¶

Problem

\(p\) is a permutation. The convenience is the number of pairs \((x, y)\) such that you can get from \(x\) to \(y\) (including \(x = y\)). You may change at most two values \(p_i\), and \(p\) must stay a permutation. Find the largest convenience.

Inside a cycle of length \(L\), every node reaches every node, so the cycle gives \(L^2\) pairs. The convenience is \(\sum L^2\).
Changing two values can join two cycles into one.
Joining lengths \(a\) and \(b\) adds \((a + b)^2 - a^2 - b^2 = 2ab > 0\). That is always a gain, and the biggest gain comes from the two longest cycles.

Sample 2: p = [1, 5, 4, 3, 2] has cycles of length \(1, 2, 2\). Join the two \(2\)s: \(4^2 + 1^2 = 17\).

def solve():
    n = int(input())
    p = [0] + list(map(int, input().split()))

    lens = []
    visited = [False] * (n + 1)
    for i in range(1, n + 1):
        if visited[i]:
            continue

        length = 0
        cur = i
        while not visited[cur]:
            visited[cur] = True
            length += 1
            cur = p[cur]
        lens.append(length)

    lens.sort()
    if len(lens) >= 2:
        b = lens.pop()
        a = lens.pop()
        lens.append(a + b)

    ans = 0
    for x in lens:
        ans += x * x
    print(ans)


solve()

Only one test case here, so there is no for _ in range(t) around solve().

7.2 G · 1027D · Mouse Hunt (rating 1700)¶

Problem

A mouse in room \(i\) runs to room \(a_i\) one second later. A trap in room \(i\) costs \(c_i\). You do not know where the mouse starts. What is the cheapest set of traps that is sure to catch it?

This is the first problem where \(a\) is not a permutation, so the graph has tails.

Wherever the mouse starts, it ends up on some cycle and runs round it forever.
So every cycle needs a trap, and one per cycle is enough: a mouse on a tail reaches the cycle and steps on it.
Put it in the cheapest room of the cycle. Answer = sum over all cycles of the smallest \(c\) on that cycle.

The cheapest room overall is not the answer

Sample 2: c = [1, 10, 2, 10], a = [2, 4, 2, 2]. The cycle is \(\{2, 4\}\); rooms \(1\) and \(3\) are on tails. A trap in room \(1\) never catches a mouse that starts in room \(2\). The answer is \(10\).

Why one visited list is not enough any more. With a permutation, a walk always stops at its own start. With tails, a walk can also stop on a node from an earlier walk. Sample 1, a = [1, 3, 4, 3, 3]: from \(5\) we reach \(3\), which was visited while walking from \(2\). That is not a new cycle, just a tail joining an old one, and a boolean cannot tell the two cases apart. So use three states:

`state[v]`	meaning
`0`	not visited yet
`1`	on the path we are walking right now
`2`	finished, its cycle was already handled

When the walk stops at cur: state[cur] == 1 means a new cycle through cur; state[cur] == 2 means nothing new.

def solve():
    n = int(input())
    c = [0] + list(map(int, input().split()))
    a = [0] + list(map(int, input().split()))

    state = [0] * (n + 1)
    ans = 0
    for i in range(1, n + 1):
        if state[i] != 0:
            continue

        path = []
        cur = i
        while state[cur] == 0:
            state[cur] = 1
            path.append(cur)
            cur = a[cur]

        if state[cur] == 1:
            # cur is on the current path -> we just found a new cycle
            best = c[cur]
            v = a[cur]
            while v != cur:
                best = min(best, c[v])
                v = a[v]
            ans += best

        for v in path:
            state[v] = 2

    print(ans)


solve()

Walk round the cycle starting from cur, not from i: i may be on a tail. A self-loop (\(a_i = i\)) is a cycle of length \(1\).

The other way to find the cycles, peeling the tails off with in-degrees, is in Topological Sorting §3 (H, H2 and I from the same lesson).

8. Common mistakes¶

Resetting vis inside the loop when you meant to share it

Creating vis inside for i in ... brings back \(O(n^2)\). That is right for Badge and wrong for Books Exchange (hard).

Checking vis but never setting it

The bug from §5.2. The code still prints correct answers, so only the time limit tells you.

if cur in members

in on a list scans the whole list, \(O(n)\) each time, so the walk becomes \(O(n^2)\) again. Use the vis list. More costs like this are in Complexity §2.5.

Mixing 0-indexed and 1-indexed

With p = [0] + [...] everything is 1-indexed: vis and the answers need size n + 1 and the loop is range(1, n + 1). With int(z) - 1 everything is 0-indexed and you add 1 when printing.

One boolean visited on a graph with tails

Stopping on a visited node no longer means a new cycle (§7.2). Use the three states, and set the whole path to 2 at the end.

Recursion

A DFS that follows p recursively crashes on a cycle of length \(2 \cdot 10^5\). These problems never need recursion.

while cur != i on a graph that is not a permutation

See the warning in §5.2. First check the statement: does it say permutation, or only \(1 \le a_i \le n\)?

9. Practice¶

Set 13 (USACO-Raymond-13-FunctionalGraph). Homework from 11 Oct: A–E accepted on your own account. A, B and C were solved in class. D is §5.2 with one change, and E is §6.

Problem	Set	Rating	Idea
1020B · Badge	13 · A	1000	§4
1249B1 · Books Exchange (easy)	13 · B	1000	§5.1
1249B2 · Books Exchange (hard)	13 · C	1300	§5.2
2008D · Sakurako's Hobby	13 · D	1100	homework: §5.2, but count the black members instead of `len(members)`
2033E · Sakurako, Kosuke, and the Permutation	13 · E	1400	§6
884C · Bertown Subway	13 · F	1500	§7.1
1027D · Mouse Hunt	13 · G	1700	§7.2
2044G1 · Medium Demon Problem (easy)	13 · H	1700	Topological Sorting §3.3
2044G2 · Medium Demon Problem (hard)	13 · H2		Topological Sorting §3.4
1872F · Selling a Menagerie	13 · I	1800	Topological Sorting §3.5

Credits & licenses

Everything on this page is ours. The code in §4 and §5 is what we wrote in class on 11 Oct; §7 is from 18 Oct.
Further reading: USACO Guide — Introduction to Functional Graphs (nothing is copied from it).

Functional Graphs¶

1. What problem does it solve?¶

2. The shape¶

2.1 Degree, in-degree, out-degree¶

2.2 The picture from class¶

2.3 Special case: permutations¶

2.4 Indices¶

3. Template¶

4. Worked solution — Badge¶

5. Lesson of 11 Oct — Books Exchange¶

5.1 1249B1 · Books Exchange (easy) (13 · B, rating 1000)¶

5.2 1249B2 · Books Exchange (hard) (13 · C, rating 1300)¶

5.3 List or dictionary for vis?¶

6. Idea only — 2033E · Sakurako, Kosuke, and the Permutation (13 · E, rating 1400)¶

7. Lesson of 18 Oct — F and G¶

7.1 F · 884C · Bertown Subway (rating 1500)¶

7.2 G · 1027D · Mouse Hunt (rating 1700)¶

8. Common mistakes¶

9. Practice¶

5.3 List or dictionary for `vis`?¶