NEERC/exclusive/exclusive_gk.java

   1 import java.util.*;
   2 import java.io.*;
   3
   4 class exclusive_gk {
   5     static Scanner in;
   6     static PrintWriter out;
   7
   8     final static char MIN_CH = 'L';
   9     final static char MAX_CH = 'Z';
  10     final static int MAX_N = MAX_CH - MIN_CH + 1;
  11
  12     int[] minColoring = new int[1 << MAX_N];
  13     int[] p = new int[1 << MAX_N];
  14     boolean[] forbidden = new boolean[1 << MAX_N];
  15
  16     private int minColoring(int mask) {
  17         if (minColoring[mask] == Integer.MAX_VALUE) {
  18                 int result = minColoring[mask];
  19                 for (int j = mask; j > 0; j = mask & (j - 1)) {
  20                         if (!forbidden[j] && result > minColoring(mask & ~j) + 1) {
  21                                 result = minColoring[mask & ~j] + 1;
  22                                 p[mask] = j;
  23                         }
  24                 }
  25                 minColoring[mask] = result;
  26         }
  27         return minColoring[mask];
  28         }
  29
  30     void run() throws IOException {
  31         int n = in.nextInt();
  32
  33         int[][] locks = new int[n][2];
  34         for (int i = 0; i < n; i++) {
  35                 locks[i][0] = in.next().charAt(0) - MIN_CH;
  36                 locks[i][1] = in.next().charAt(0) - MIN_CH;
  37         }
  38
  39         for (int i = 0; i < n; i++) {
  40                 int mask = (1 << locks[i][0]) | (1 << locks[i][1]);
  41                         for (int j = 0; j < 1 << MAX_N; j++) {
  42                                 forbidden[j] |= (j & mask) == mask;
  43                         }
  44         }
  45
  46         Arrays.fill(minColoring, Integer.MAX_VALUE);
  47         minColoring[0] = 0;
  48
  49         out.println(minColoring((1 << MAX_N) - 1) - 2);
  50
  51         int[] colors = new int[MAX_N];
  52         int color = 1;
  53         for (int mask = (1 << MAX_N) - 1; mask != 0; mask &= ~p[mask]) {
  54                 for (int j = 0; j < MAX_N; j++) {
  55                         if (((p[mask] >> j) & 1) != 0) {
  56                                 colors[j] = color;
  57                         }
  58                 }
  59                 color++;
  60         }
  61
  62         for (int i = 0; i < n; i++) {
  63                 int q = colors[locks[i][0]] < colors[locks[i][1]] ? 0 : 1;
  64                 out.println((char) (locks[i][q] + MIN_CH) + " " + (char) (locks[i][1 - q] + MIN_CH));
  65         }
  66     }
  67
  68         public static void main(String[] args) throws Exception {
  69         in = new Scanner(new File("exclusive.in"));
  70         out = new PrintWriter("exclusive.out");
  71
  72         new exclusive_gk().run();
  73
  74         in.close();
  75         out.close();
  76     }
  77 }