Leonardo’s Notebook
time limit per test 1 second memory limit per test 256 megabytes
Write a program that takes a permutation of the English alphabet as input and decides if it may be the result of performing some permutation twice.

传送门:POJ3128

Input

The input begins with a positive number on a line of its own telling the number of test cases (at most 500). Then for each test case there is one line containing a permutation of the 26 capital letters of the English alphabet.

Output

For each test case, output one line containing Yes if the given permutation can result from applying some permutation twice on the original alphabet string ABC...XYZ, otherwise output No.
## Sample Input
1
2
3
2
QWERTYUIOPASDFGHJKLZXCVBNM
ABCDEFGHIJKLMNOPQRSTUVWXYZ
## Sample Output
1
2
No
Yes
## 题解
题意:给出一个置换,判断其能否开方 图个眼熟 开方的话不需要管长度为奇数的循环节的个数 要注意的是长度为偶数的循环节的个数是不是都是偶数 举个例子 长度为2的循环节有2个 那就可以 长度为2的循环节有3个 就不行 这里的循环节我用并查集来做 感觉更方便点= =
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.io.*;  
import java.util.*;
public class Main {
static int[]pre;
static int[]sum;
public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
int n=sc.nextInt();
while(sc.hasNext()){
String s=sc.next();
pre=new int[26];
sum=new int[26];
for(int i=0;i<26;i++){
pre[i]=i;
sum[i]=1;
}
for(int i=0;i<26;i++){
union(i,s.charAt(i)-'A');
}
int count=0;
boolean flag=true;
int[]js=new int[26];
for(int i=0;i<26;i++){
if(pre[i]==i){
if(sum[i]%2==0){
js[sum[i]]++;
}
}
}
for(int i=2;i<26;i+=2){
if(js[i]%2!=0){
flag=false;
}
}
if(flag)pw.println("Yes");
else pw.println("No");
pw.flush();
}

}
static int find(int x){
if(pre[x]==x) return x;
int root=find(pre[x]);
return pre[x]=root;
}
static void union(int a,int b){
int fa=find(a);
int fb=find(b);
if(fa!=fb){
pre[fa]=fb;
sum[fb]+=sum[fa];
}
}
}