Description
给定一个序列 \(a_1, a_2, \ldots, a_n\)，构造一个长度为 \(k\) 序列 \(b_1, b_2, \ldots, b_k\)，其中 \(k\) 为任意正整数，使得：
- 在 \(a\) 序列中删除下标为 \(b_1, b_2, \ldots, b_k\) 的数后，\(a\) 与 \(b\) 两个序列完全相同。一个下标可以被删除多次，即序列 \(b\) 中的元素不一定两两不同。
Solution
发现如果一个值为 \(a_i\) 的数最终没被删掉，那么下标 \(i\) 至少被删了一次，然后如果一个下标 \(i\) 被删掉了，那么一定存在一个 \(j\) 使得 \(a_j = i\)。
所以考虑对于每个 \(i\)，从 \(i\) 向 \(a_i\) 连边，然后用颜色 \(col_i\) 刻画一个点 \(i\) 是否被删了至少一次，\(col = 1\) 表示被删过至少一次，称为黑点，\(col = 0\) 表示没被删过，称为白点。
容易发现这样连成的图为外向基环树，并且图有如下性质：
- 任何一个白点都连向一个黑点。
- 任何一个黑点都被一个白点所指向。
考虑如何构造每个点的颜色，首先显然任意叶子节点都满足 \(col = 0\)，然后可以用叶子节点的颜色往上推。
具体的，对于树上的一个点，如果它有一个儿子为白点，那么它一定是黑点，否则我们默认它是白点。
对于环上的点，部分已经被自己的儿子确定，为黑点，其余的可能为黑点，也可能为白点，观察什么情况下环上的点会不符合要求，发现如果环上有连续两个白点，那么就不合法。
所以我们破环成链，并把每一段连续的白点拿出来，把其中一半的点变成黑点，此时就不会出现白点指向白点的情况了。
最后，我们已经求出了每个点的颜色，那么所有的白点，也就是未被删除的点，就构成的所求的 \(b\) 数组。
关于本做法的正确性，考虑这种构造什么情况下会出现无解，发现只会出现在一个点为自环，其余若干（偶数）个点依次链接，形成一条长度为奇数的链，可以证明此时不存在解。否则按照上述的黑白染色一定能构造出一组合法解。
Code
#include <iostream>
#include <numeric>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
using LL = long long;
const int N = 2e5 + 5;
const int Mod = 998244353;
int n;
int a[N], d[N], col[N];
vector<int> t[N], e[N], ans;
queue<int> q;
bool vis[N];
int arr[N * 2], len;
void dfs (int u) {
if (vis[u]) return;
vis[u] = 1, arr[++len] = u;
dfs(a[u]);
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T = 1;
for (int tt = 1; tt <= T; ++tt) {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i], ++d[a[i]];
t[a[i]].push_back(i);
e[i].push_back(a[i]);
}
for (int i = 1; i <= n; ++i) {
if (!d[i]) q.push(i);
}
for (; !q.empty(); q.pop()) {
int u = q.front(); vis[u] = 1;
col[a[u]] |= !col[u];
if (!(--d[a[u]])) q.push(a[u]);
}
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
len = 0, dfs(i);
bool fl = 0;
for (int j = 1; j <= len; ++j) {
fl |= col[arr[j]];
}
if (!fl) {
for (int j = 2; j <= len; j += 2) {
col[arr[j]] = 1;
}
}
else {
copy(arr + 1, arr + len + 1, arr + len + 1);
int la = 0;
for (int j = 1; j <= len * 2; ++j) {
if (col[arr[j]]) {
if (la > len) break;
if (la) {
for (int k = la + 2; k < j; k += 2) {
col[arr[k]] = 1;
}
}
la = j;
}
}
}
}
}
for (int i = 1; i <= n; ++i) {
bool fl = 0;
if (col[i]) {
for (auto v : t[i])
fl |= !col[v];
}
else {
ans.push_back(a[i]);
fl = col[a[i]];
}
if (!fl) {
cout << -1 << '\n';
return 0;
}
}
cout << ans.size() << '\n';
for (auto i : ans) {
cout << i << ' ';
}
cout << '\n';
}
return 0;
}