数组补全（秋季每日一题 10）

给定一个 $1\sim n$ 的排列 $f_1,f_2,\dots ,f_n$。

已知，对于 $1\le i\le n$，$f_i\ne i$ 始终成立。

现在，因为一些原因，数组中的部分元素丢失了。

请你将数组丢失的部分补全，要求数组在补全后仍然是一个 $1\sim n$ 的排列，并且对于 $1\le i\le n$， $f_i\ne i$ 均成立。

输入格式
第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $f_1,f_2,\dots ,f_n$。如果 $f_i=0$，则表示 $f_i$ 已经丢失，需要补全。

输出格式
每组数据一行，输出补全后的 $f$ 数组，整数之间空格隔开。

如果方案不唯一，则输出任意合理方案即可。

数据范围
$1\le T\le 100，$
$2\le n\le 2\times 10^5，$
$0\le f_i\le n，$至少两个 $f_i$ 为 $0$。
同一测试点内所有 $n$ 的和不超过 $2\times 10^5$。
数据保证有解。

输入样例：

3
5
5 0 0 2 4
7
7 0 0 1 4 0 6
7
7 4 0 3 0 5 1
1
2
3
4
5
6
7

输出样例：

5 3 1 2 4
7 3 2 1 4 5 6
7 4 2 3 6 5 1
1
2
3

---

1. 记录孤立点
2. 将孤立点插入任意一个开环中
3. 将开环闭合
4. 如何没有一个开环，则将孤立点集自成环

#include
#include
#include

using namespace std;

const int N = 200010;

int n;
int pre[N], ne[N];
bool st[N]; // 标记孤立点

int main(){
    
    int t;
    scanf("%d", &t);
    
    while(t--){
        
        scanf("%d", &n);
        memset(ne, 0, 4*(n+1));
        memset(pre, 0, 4*(n+1));
        memset(st, 0, n+1); // 孤立点
        
        for(int i = 1; i <= n; i++) scanf("%d", &ne[i]), pre[ne[i]] = i;
        
        vector<int> v;
        for(int i = 1; i <= n; i++)
            if(!ne[i] && !pre[i]){ 
                v.push_back(i);
                st[i] = true;
            }
            
        bool flag = false;
        for(int i = 1; i <= n; i++){
            if(!st[i] && ne[i] && !pre[i]){ // 开环的头节点
                
                int u = ne[i]; // 尾
                while(ne[u]) u = ne[u];
                
                if(!flag){
                    for(int j = 0; j < v.size(); j++){
                        
                        ne[u] = v[j];
                        u = ne[u];
                    }
                    flag = true;
                }
                
                ne[u] = i;  // 连成环
            }
        }
        
        int hh = 0, tt = 0;
        if(!flag){  // 如过孤立点没有被插入任何一个开环，则他们自己成环
            
            for(int i = 0; i < v.size(); i++)
                if(!hh && !tt) hh = tt = v[i];
                else ne[tt] = v[i], tt = v[i];
            
            ne[tt] = hh;
        }
        
        for(int i = 1; i <= n; i++) printf("%d ", ne[i]);
        puts("");
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69