考虑将所有的 \(i\) 指向 \(a_i\),将会建出一张基环内向树。
对于一个节点 \(i\),假若最终我们未圈出它,那么我们称我们选择了 \(i\) 的出边;否则是未选择。
不难发现,最终答案合法当且仅当:所有未选择出边的点,它的入边最少有一条被选择了;所有选择了出边的点,它所有的入边都没被选择。
由于所有叶节点只能选择它的出边,于是考虑对于基环树自底向上贪心,最终对于剩下的环进行处理。
无解的情况,就是在我们处理之后发现有节点并未在过程中处理成功。
代码可以使用拓扑排序简易实现。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 1e6 + 10;
int n, a[N], b[N], in[N], id[N], vis[N], cnt[N];
queue<int> q;
vector<int> ans;
int main(){
scanf("%d", &n);
FL(i, 1, n) id[i] = i;
FL(i, 1, n) scanf("%d", &a[i]), in[a[i]]++;
FL(i, 1, n) if(!in[i]) q.push(i), vis[i] = 1;
while(!q.empty()){
int u = q.front(), v = a[u]; q.pop();
if(vis[v]) continue; ans.emplace_back(a[u]);
vis[v] = 1, in[a[v]]--;
if(!in[a[v]]) vis[a[v]] = 1, q.push(a[v]);
}
FL(i, 1, n) if(!vis[i])
for(int u = i; a[u] != u && !vis[a[u]]; u = a[a[u]])
ans.emplace_back(a[u]), vis[u] = vis[a[u]] = 1;
FL(i, 1, n) if(!vis[i]){printf("-1\n"); return 0;}
int tot = 0;
for(const int &x: ans) b[x] = 1;
FL(i, 1, n) tot += b[i];
printf("%d\n", n - tot);
FL(i, 1, n) if(!b[i]) printf("%d ", a[i]);
return 0;
}