NEERC/exclusive/exclusive_petr.java

   1 import java.io.BufferedReader;
   2 import java.io.FileReader;
   3 import java.io.PrintWriter;
   4 import java.io.IOException;
   5 import java.util.StringTokenizer;
   6
   7 public class exclusive_petr implements Runnable {
   8     private void solve() throws IOException {
   9         int n = nextInt();
  10         int m = 'Z' - 'L' + 1;
  11         boolean[][] e = new boolean[m][m];
  12         int[][] edges = new int[n][];
  13         for (int i = 0; i < n; ++i) {
  14             int a = nextToken().charAt(0) - 'L';
  15             int b = nextToken().charAt(0) - 'L';
  16             edges[i] = new int[]{a, b};
  17             e[a][b] = true;
  18             e[b][a] = true;
  19         }
  20         boolean[] sane = new boolean[1 << m];
  21         for (int i = 0; i < sane.length; ++i) {
  22             sane[i] = true;
  23             for (int j = 0; j < m; ++j)
  24                 if (((i >> j) & 1) != 0)
  25                     for (int k = j + 1; k < m; ++k)
  26                         if (((i >> k) & 1) != 0)
  27                             if (e[j][k])
  28                                 sane[i] = false;
  29         }
  30         int[] cnt = new int[1 << m];
  31         int[] prev = new int[1 << m];
  32         cnt[0] = 0;
  33         for (int i = 1; i < cnt.length; ++i) {
  34             cnt[i] = Integer.MAX_VALUE;
  35             prev[i] = -1;
  36             for (int j = i; j > 0; j = (j - 1) & i) {
  37                 if (sane[j]) {
  38                     if (cnt[i ^ j] + 1 < cnt[i]) {
  39                         cnt[i] = cnt[i ^ j] + 1;
  40                         prev[i] = j;
  41                     }
  42                 }
  43             }
  44         }
  45         int[] step = new int[m];
  46         int cur = cnt.length - 1;
  47         while (cur > 0) {
  48             int set = prev[cur];
  49             for (int j = 0; j < m; ++j)
  50                 if (((set >> j) & 1) != 0)
  51                     step[j] = cnt[cur];
  52             cur ^= set;
  53         }
  54         writer.println(cnt[cnt.length - 1] - 2);
  55         for (int i = 0; i < n; ++i)
  56             if (step[edges[i][0]] < step[edges[i][1]]) {
  57                 writer.println((char) ('L' + edges[i][0]) + " " + (char) ('L' + edges[i][1]));
  58             } else {
  59                 writer.println((char) ('L' + edges[i][1]) + " " + (char) ('L' + edges[i][0]));
  60             }
  61     }
  62
  63
  64     public static void main(String[] args) throws InterruptedException {
  65         Thread thread = new Thread(new exclusive_petr());
  66         thread.start();
  67         thread.join();
  68     }
  69
  70     static final String TASK_ID = "exclusive";
  71     static final String IN_FILE = TASK_ID + ".in";
  72     static final String OUT_FILE = TASK_ID + ".out";
  73     BufferedReader reader;
  74     StringTokenizer tokenizer;
  75     PrintWriter writer;
  76
  77     public void run() {
  78         try {
  79             reader = new BufferedReader(new FileReader(IN_FILE));
  80             tokenizer = null;
  81             writer = new PrintWriter(OUT_FILE);
  82             solve();
  83             reader.close();
  84             writer.close();
  85         } catch (Exception e) {
  86             e.printStackTrace();
  87             System.exit(1);
  88         }
  89     }
  90
  91     int nextInt() throws IOException {
  92         return Integer.parseInt(nextToken());
  93     }
  94
  95     long nextLong() throws IOException {
  96         return Long.parseLong(nextToken());
  97     }
  98
  99     double nextDouble() throws IOException {
 100         return Double.parseDouble(nextToken());
 101     }
 102
 103     String nextToken() throws IOException {
 104         while (tokenizer == null || !tokenizer.hasMoreTokens()) {
 105             tokenizer = new StringTokenizer(reader.readLine());
 106         }
 107         return tokenizer.nextToken();
 108     }
 109 }