Algorithm :-
1. Odd length cycles are OK.
2. The graph should have two even length cycles of the same length if even cycles exist. (There may be multiple even cycles).
3. Self loops are OK.
Point #2:
Consider an alphabet having only 6 letters i.e. ABCDEF. Now we have to apply the same permutation twice to get "CDEABF". The permutation we apply is "BCDAEF". Applying it twice (steps):-
|--->CDABEF
P
|--->BCDAEF
P
|----ABCDEF
Where P stands for the application of the permutation "BCDAEF". Now if we only consider the final alphabet string and the original one,
CDABEF
ABCDEF
Notice our even length cycle "BCDA" has split up into two even cycles of equal length. (CA and DB).
You can similarly figure out that odd length cycles remain odd length cycles and of course, self loops have no effect.
Self loops:
There are two self loops in the above example E-E and F-F.
Now just write code to check whether there are even number of even length cycles. If this is the case, the answer is yes, otherwise no.
Source (Java):
1. Odd length cycles are OK.
2. The graph should have two even length cycles of the same length if even cycles exist. (There may be multiple even cycles).
3. Self loops are OK.
Point #2:
Consider an alphabet having only 6 letters i.e. ABCDEF. Now we have to apply the same permutation twice to get "CDEABF". The permutation we apply is "BCDAEF". Applying it twice (steps):-
|--->CDABEF
P
|--->BCDAEF
P
|----ABCDEF
Where P stands for the application of the permutation "BCDAEF". Now if we only consider the final alphabet string and the original one,
CDABEF
ABCDEF
Notice our even length cycle "BCDA" has split up into two even cycles of equal length. (CA and DB).
You can similarly figure out that odd length cycles remain odd length cycles and of course, self loops have no effect.
Self loops:
There are two self loops in the above example E-E and F-F.
Now just write code to check whether there are even number of even length cycles. If this is the case, the answer is yes, otherwise no.
Source (Java):
import java.io.IOException; import java.io.InputStream; import java.util.InputMismatchException; public class LEONARDO { public static void main(String[] args){ int n = IO.nextInt(); String REF = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; while(n-->0){ String s = IO.nextString(); int[] pos = new int[256]; for(int i=0;i<s.length();++i){ pos[s.charAt(i)] = i; } boolean m[] = new boolean[256]; int cyclesReg[] = new int[26]; for(int i=0;i<s.length();++i){ char c = s.charAt(i); boolean f = false; int length =0 ; while(!m[c]){ f = true; length++; m[c] = true; int p = pos[c]; c = REF.charAt(p); } if(f){ cyclesReg[length]++; } } boolean f = true; for(int i=0;i<cyclesReg.length;++i){ if(i%2==0 && cyclesReg[i]%2!=0){f = false;break;} } if(f)IO.println("Yes"); else IO.println("No"); } } private static class IO { private static InputStream stream = System.in; private static byte[] buf = new byte[1024]; private static int curChar, numChars; private static int read() { if (numChars == -1)throw new InputMismatchException(); if (curChar >= numChars) { curChar = 0; try { numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0)return -1; } return buf[curChar++]; } public static int nextInt() { int c = read(); while (isSpaceChar(c)) c = read(); int sgn = 1; if (c == '-') { sgn = -1; c = read(); } int res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res *= 10; res += c - '0'; c = read(); } while (!isSpaceChar(c)); return res * sgn; } public static char nextChar() { int c = read(); while (isSpaceChar(c)) c = read(); return (char) c; } private static String nextString(){ int c = read(); while(isSpaceChar(c))c=read(); StringBuilder sb = new StringBuilder(); do{ sb.append((char)c); }while(!isSpaceChar((c=read()))); return sb.toString(); } private static boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } private static void println(Object... a){ for(Object o:a)System.out.print(o); System.out.println(); } } }
