环图解法

Python3 代码

T = int(input())

for i in range(T):
    n = int(input())

    nums = [0] + list(map(int, input().split()))

    # p: 构造i -> fi的图
    # q: 构造fi -> i的图
    # st: 判断处理过的数
    p = [0] * (n + 1)
    q = [0] * (n + 1)
    st = [0] * (n + 1)

    # 预处理数组
    for i in range(1, n+1):
        # i -> fi
        p[i] = nums[i]
        # fi -> i
        q[nums[i]] = i

    # 判断是否处理过所有点
    flag = False
    # 遍历每一个点
    for i in range(1, n+1):
        # 若该点被处理过或为孤立点，则continue
        if st[i] or not p[i]:
            continue

        # 标记该点
        st[i] = 1

        # 寻找该点所在环的头尾节点
        x = y = i
        while p[x] and not st[p[x]]:
            x = p[x]
            st[x] = 1

        while q[y] and not st[q[y]]:
            y = q[y]
            st[y] = 1

        # 若该环不存在缺口，则continue
        if p[x] == y:
            continue

        # 避免重复处理
        if not flag:
            flag = True

            for j in range(1, n+1):
                # 找到所有孤立点
                if not p[j] and not q[j]:
                    st[j] = True
                    # 连接孤立点
                    p[x] = j
                    x = j

        # 头尾相连
        p[x] = y

    # 若不是所有点都被处理过
    if not flag:
        # 将剩下的所有孤立点再构成环图
        x = y = 0
        for i in range(1, n+1):
            # 找到孤立点
            if not p[i]:
                # 定义新环图的起点与终点
                if not x and not y: 
                    x = y = i
                else:
                    p[x] = i
                    x = i

        # 头尾相连
        p[x] = y

    # 输出结果
    print(' '.join(map(str, p[1:])))