[搬家]Codeforces 576B
这一题.....
我们看样例..
Sample test(s)
input
4
4 3 2 1
output
YES
4 1
4 2
1 3
input
3
3 1 2
output
NO
嗯,我们看样例1的解释
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.
这个解释说明了,第一个样例(4,1)-->(1,4)
这是个二元环!
我们考虑:
有一个一元环的情况下,显然是可以的:这个点连上其他所有
有若干个二元环的情况下,也是可以的,姿势同样例1
别的情况呢?
我觉得都是不可以的
Wrong Answer on test 9......
实际上..
在有一个2元环的情况下,可以带一堆偶数元环
例如(1 2)带(3 4 5 6)的姿势是这样的
1 -- 3
2 -- 4
1 -- 5
2 -- 6
(1 -- 2)
那么代码如下;
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[100005];
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
scanf("%d",&n);
int i;
for (i=0;i<n;i++)
{
scanf("%d",&a[i]);
a[i]--;
}
for (i=0;i<n;i++)
{
if (a[i]==i)
{
puts("YES");
int j;
for (j=0;j<n;j++)
{
if (j!=i)
{
printf("%d %d\n",i+1,j+1);
}
}
return 0;
}
}
int t1=-1;
int t2=-1;
for (i=0;i<n;i++)
{
if (a[i]==-1) continue;
if (a[a[i]]==-1) continue;
int cir_len=1;
int now=a[i];
for (;now!=i;)
{
int t=a[now];
if (cir_len%2==1) a[now]=-1;
now=t;
cir_len++;
}
if (cir_len%2==1)
{
puts("NO");
return 0;
}
if (cir_len==2)
{
t1=i;
t2=a[i];
}
}
if (t1==-1)
{
puts("NO");
return 0;
}
puts("YES");
printf("%d %d\n",t1+1,t2+1);
for (i=0;i<n;i++)
{
if (i==t1) continue;
if (i==t2) continue;
if (a[i]==-1) continue;
a[a[i]]=-1;
printf("%d %d\n",t1+1,i+1);
printf("%d %d\n",t2+1,a[i]+1);
}
return 0;
}
评论 (0)