NEERC/inspection/inspection_rs_wa.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 public class inspection_rs_wa implements Runnable {
   5         private BufferedReader in;
   6         private PrintWriter out;
   7
   8         private void check(boolean expr, String msg) {
   9                 if (!expr) {
  10                         throw new Error(msg);
  11                 }
  12         }
  13
  14         private void checkBounds(int n, int low, int hi, String nStr) {
  15                 check((low <= n) && (n <= hi), nStr + " is not in [" + low + ", " + hi + "]");
  16         }
  17
  18         private boolean[][] go;
  19         private boolean[] mark;
  20         private int[] topsort;
  21         private int n, count;
  22
  23         private List<List<Integer>>[] paths;
  24
  25         private void dfs(int u) {
  26                 mark[u] = true;
  27                 for (int v = 0; v < n; v++) {
  28                         if (!mark[v] && go[u][v]) {
  29                                 dfs(v);
  30                         }
  31                 }
  32                 topsort[--count] = u;
  33         }
  34
  35         @SuppressWarnings("unchecked")
  36         private void solve() throws IOException {
  37                 n = Integer.parseInt(in.readLine());
  38                 checkBounds(n, 1, 100, "n");
  39                 go = new boolean[n][n];
  40                 for (int i = 0; i < n; i++) {
  41                         StringTokenizer st = new StringTokenizer(in.readLine());
  42                         int w = Integer.parseInt(st.nextToken());
  43                         for (int j = 0; j < w; j++) {
  44                                 int u = Integer.parseInt(st.nextToken()) - 1;
  45                                 check(u != i, "Edge from vertix to itself");
  46                                 check(!go[i][u], "Duplicate edges");
  47                                 go[i][u] = true;
  48                         }
  49                 }
  50                 mark = new boolean[n];
  51                 topsort = new int[n];
  52                 count = n;
  53                 for (int i = 0; i < n; i++) {
  54                         if (!mark[i]) {
  55                                 dfs(i);
  56                         }
  57                 }
  58
  59                 for (int i = 0; i < n; i++) {
  60                         for (int j = i + 1; j < n; j++) {
  61                                 check(!go[topsort[j]][topsort[i]], "graph is not acyclic");
  62                         }
  63                 }
  64
  65                 paths = new List[n];
  66                 for (int i = 0; i < n; i++) {
  67                         paths[i] = new ArrayList<List<Integer>>();
  68                 }
  69                 int totalPaths = 0;
  70                 for (int ii = 0; ii < n; ii++) {
  71                         int i = topsort[ii];
  72                         for (int jj = 0; jj < ii; jj++) {
  73                                 int j = topsort[jj];
  74                                 if (!go[j][i]) {
  75                                         continue;
  76                                 }
  77                                 if (!paths[j].isEmpty()) {
  78                                         List<Integer> path = paths[j].get(paths[j].size() - 1);
  79                                         paths[j].remove(paths[j].size() - 1);
  80
  81                                         path.add(i);
  82                                         paths[i].add(path);
  83                                         continue;
  84                                 }
  85
  86                                 List<Integer> path = new ArrayList<Integer>();
  87                                 path.add(j);
  88                                 path.add(i);
  89                                 paths[i].add(path);
  90                                 totalPaths++;
  91                         }
  92                 }
  93
  94                 out.println(totalPaths);
  95                 for (int i = 0; i < n; i++) {
  96                         for (List<Integer> path: paths[i]) {
  97                                 for (int j: path) {
  98                                         out.print((j + 1) + " ");
  99                                 }
 100                                 out.println();
 101                         }
 102                 }
 103         }
 104
 105         public static void main(String[] args) {
 106                 new Thread(new inspection_rs_wa()).start();
 107         }
 108
 109         public void run() {
 110                 String problem = getClass().getName().split("_")[0];
 111                 try {
 112                         in = new BufferedReader(new FileReader(new File(problem + ".in")));
 113                         out = new PrintWriter(new File(problem + ".out"));
 114                         solve();
 115                         in.close();
 116                         out.close();
 117                 } catch (IOException e) {
 118                         e.printStackTrace();
 119                         System.exit(1);
 120                 }
 121         }
 122 }