Composition of permutations – the group product
Haskell, 157 148 bytes

EDIT:


-9 bytes: That could indeed be golfed more. Removed redundant parentheses around p++q. Swapped argument order of g. Got rid of d by starting iterate with p x, after which takeWhile no longer tied with fst + span. Made iterate infix.


Doing this while I'm late... probably can golf some more.

It was simpler, and seemed to be allowed, so the output includes single-element cycles.



q#p=g(p++q&gt;&gt;=id)$f q.f p
f p a=last$a:[y|c&lt;-p,(x,y)&lt;-zip(0:c)(c++c),x==a]
g(x:l)p|c&lt;-x:fst(span(/=x)$p`iterate`p x)=c:g[x|x&lt;-l,x`notElem`c]p
g[]p=[]


Try it online!

How it works:


# is the main function. q#p takes two lists of lists of numbers, and returns a similar list. The tests seem to have Q before P so I used the same order.
f p converts the permutation p from disjoint cycle form to a function, after which f q and f p can be composed with the usual composition operator ..


The list comprehension iterates through the cycles c, searching for a and finding its successor. If the comprehension finds nothing, a is just returned.
zip(0:c)(c++c) is a list of pairs of elements of c and their successors. Since the question lets us "start at one" we can use 0 as a dummy value; it's cheaper to prepend that to zip's first argument than to use tail on the second.

g l p takes a list l of elements, and a permutation function p, and returns the list of cycles touching the elements.


Here c is the cycle containing the first element x of the list, the other elements of c are found by iterating from p x until x is found again. When recursing to find the remaining cycles, all elements of c are first removed with a list comprehension.