CF 1283C Friends and Gifts

原文

抽象出来的题意:

解法:

我们通过观察发现要保证自己不会给到自己元素 那么一定不会出现自环(一条 顶点 与自身连接的 边), 所以我们可以把给定的序列看成一个图 ,这个图可能出现多个环,并且每一个环相对独立,所以 ,我们有 :
如果发现有独立的点没有任何入度和出度(也就是从来没有被访问过的点) 那把他加入任意一个没有闭口的环,然后再将没有闭口的环闭口即可. 但是可能会出现整个图里面只包含闭口的环和一些独立点,这个时候我们只需要把这些点单独构造出一个环即可.(例如 2 1 0 0 0 (2 和 1 是一个闭口环 3 4 5 是单独的点,我们只需要把3 4 5 连成一个图即可))

我们可以重头开始模拟,当发现当前位置的值不为0,那他肯定有一条出度,我们可以继续迭代下去,知道迭代到当前点没有出度或者开头, 当我们在迭代一个环的一小部分时,可以证明的是我们把v数组打上起始元素的时间戳记录这一个环是从哪一个开始的,当数组遍历完毕, g数组值为0,并且v数组不为0,则肯定是一个未闭口环 ,然后我们将其链接起即可

#include<bits/stdc++.h>
const int N = 2e5+111;
using namespace std;
int t,n,m,g[N],v[N];
int main(){
    //cin>>t;//while(t--){
    cin>>n;queue<int> que;memset(v,0,sizeof v);for(int i=1;i<=n;i++) cin>>g[i];for(int i=1;i<=n;i++){
    if(v[i]||!g[i]) continue;int x = i;while(g[x]&&v[g[x]]!=i){
    x=g[x];v[x]=i;}v[i]=i;}for(int i=1;i<=n;i++) if(v[i]==0) que.push(i);int f=1;for(int i=1;i<=n;i++){
    if(!f) {
    if(g[i]==0) g[i]=v[i];continue;}if(g[i]==0&&v[i]!=0){
    int tt = v[i],xx = i;while(que.size()){
    int q = que.front();que.pop();g[xx]=q;v[xx]=tt;xx=q;}g[xx]=v[i];f=0;}}if(que.size()){
    int tt = que.front();que.pop();que.push(tt);int ii = tt;while(que.size()){
    g[ii]=que.front();ii=que.front();que.pop();}}for(int i=1;i<=n;i++) cout<<g[i]<<" ";cout<<endl;//} return 0;
}