Codeforces Round #319 (Div. 1) B. Invariance of Tree

今天药忘吃喽~ 2022-08-05 08:51 127阅读 0赞

# B. Invariance of Tree #

A tree of size n is an undirected connected graph consisting of n vertices without cycles.

Consider some tree with *n* vertices. We call a tree invariant relative to permutation *p* = *p*1*p*2...*p**n*, if for any two vertices of the tree u and v the condition holds: “vertices u and v are connected by an edge if and only if vertices pu and pv are connected by an edge”.

You are given permutation p of size *n*. Find some tree size n, invariant relative to the given permutation.

### Input ###

The first line contains number *n*(1 ≤ *n* ≤ 105)— the size of the permutation (also equal to the size of the sought tree).

The second line contains permutation *p**i*(1 ≤ *p**i* ≤ *n*).

### Output ###

If the sought tree does not exist, print “NO” (without the quotes).

Otherwise, print “YES”, and then print n - 1 lines, each of which contains two integers — the numbers of vertices connected by an edge of the tree you found. The vertices are numbered from 1, the order of the edges and the order of the vertices within the edges does not matter.

If there are multiple solutions, output any of them.

### Sample test(s) ###

input  
4  
4 3 2 1  
output  
YES  
4 1  
4 2  
1 3  
input  
3  
3 1 2  
output  
NO

### Note ###

In the first sample test a permutation transforms edge (4, 1) into edge (1, 4), edge (4, 2) into edge (1, 3) and edge (1, 3) into edge (4, 2). These edges all appear in the resulting tree.

It can be shown that in the second sample test no tree satisfies the given condition.

构造题

因为样例给的比较全，所以一看就可以看出规律。

首先发现，根据样例1发现，构造这棵树需要一个长度为2的环作为中心，然后将其他环拆开分在两侧，形成一个对称的结构。  
因为是一个对称的结构，所以不能有长度为奇数的环。样例2也体现了这一点（虽然它连最基础的长度为2的环也没有。）

因为最终形成的是一个对称的图形，所以就想着如果出现了自环会如何。于是可以发现，自环的情况就是，上面的情况，将长度为2的环形成的边去掉，缩成一个点，形成一个像太阳花一样的图形，也是符合题意的。

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    
    using namespace std;
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<50
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    #define debug(a) cout << #a" = " << (a) << endl;
    #define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
    
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    #define ls (idx<<1)
    #define rs (idx<<1|1)
    #define lson ls,l,mid
    #define rson rs,mid+1,r
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    const int MAXN=100010;
    int pos1,pos2,pos3;
    int p[MAXN],o[MAXN];
    
    int main()
    {
        int n;
        read(n);
        for(int i=1;i<=n;i++)
            read(p[i]);
        for(int i=1;i<=n;i++)
        {
            if(p[i]==i) pos1=i;
            if(p[p[i]]==i)  pos2=i;
        }
        if(pos1)
        {
            puts("YES");
            for(int i=1;i<=n;i++)
                if(i!=pos1)
                    printf("%d %d\n",i,pos1);
            return 0;
        }
        else if(pos2)
        {
            pos3=p[pos2];
            for(int i=1,j;i<=n;i++)
            {
                if(o[i])    continue;
                o[i]=1;
                j=p[i];
                while(j!=i) o[i]++,j=p[j];
                j=p[i];
                while(j!=i) o[j]=o[i],j=p[j];
                if(o[i]&1)
                {
                    puts("NO");
                    exit(0);
                }
            }
            CLR(o,0);o[pos2]=o[pos3]=2;
            puts("YES");
            printf("%d %d\n",pos2,pos3);
            for(int i=1,j;i<=n;i++)
            {
                if(o[i])    continue;
                o[i]=1;
                j=p[i];
                printf("%d %d\n",pos2,i);
                while(j!=i)
                {
                    if(o[i]&1)
                        printf("%d %d\n",pos3,j);
                    else
                        printf("%d %d\n",pos2,j);
                    o[i]++;
                    j=p[j];
                }
                j=p[i];
                while(j!=i) o[j]=o[i],j=p[j];
            }
            return 0;
        }
        puts("NO");
        return 0;
    }