fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.List;
  3.  
  4. /**
  5.  * Created by Gaoyuan Chen on 5/19/2016.
  6.  */
  7. public class TopologicalOrdering {
  8.  
  9.     int n;
  10.     int len = 20;
  11.     List<Integer> offset;
  12.  
  13.     boolean dfs(List<Integer> lis, int remain)
  14.     {
  15.         if(remain == 0) return false;
  16.  
  17.         for(int i = 0; i < lis.size(); i++)
  18.             if(lis.get(i) == n)
  19.             {
  20.                 offset.add(lis.size());
  21.                 return true;
  22.             }
  23.  
  24.         for(int i = 0; i < lis.size()-1; i++)
  25.         {
  26.             int s = 0;
  27.             List<Integer> t = new ArrayList<>();
  28.             for(int j = i; j < lis.size(); j++)
  29.             {
  30.                 s += lis.get(j);
  31.                 if(s > n)
  32.                     break;
  33.                 t.add(s);
  34.             }
  35.             if(dfs(t, remain - 1))
  36.             {
  37.                 offset.add(i);
  38.                 return true;
  39.             }
  40.         }
  41.         return false;
  42.     }
  43.  
  44.     boolean solve(int _n)
  45.     {
  46.         n = _n;
  47.         List<Integer> t = new ArrayList<>();
  48.         for(int i = 1; i <= Math.min(n, len); i++)
  49.             t.add(i);
  50.         return dfs(t, len);
  51.     }
  52.  
  53.     public int[] construct(int n)
  54.     {
  55.         if(n == 1) return new int[]{1};
  56.         if(n == 4) return new int[]{5,0,2,1,2,2,3,2,4};
  57.         if(n == 5) return new int[]{5,0,1,1,2,2,3};
  58.         if(n == 720) return new int[]{6};
  59.  
  60.         offset = new ArrayList<>();
  61.         solve(n);
  62.  
  63.         int cols = 0;
  64.         for(int i = 0; i < offset.size(); i++)
  65.             cols += offset.get(i);
  66.         cols --;
  67.         int rows = offset.size();
  68.  
  69.         List<Integer> a = new ArrayList<>();
  70.         List<Integer> b = new ArrayList<>();
  71.  
  72.         for(int i = 0; i < cols - 1; i++)
  73.         {
  74.             a.add(i);
  75.             b.add(i+1);
  76.         }
  77.         for(int i = 0; i < rows - 1; i++)
  78.         {
  79.             a.add(cols + i);
  80.             b.add(cols + i + 1);
  81.         }
  82.         int node1 = -1;
  83.         int node2 = cols;
  84.         for(int i = offset.size()-1; i > 0; i--)
  85.         {
  86.             node1 += offset.get(i);
  87.             node2 ++;
  88.             if(node1 >= 0)
  89.             {
  90.                 a.add(node1);
  91.                 b.add(node2);
  92.             }
  93.         }
  94.         int[] ret = new int[2 * a.size() + 1];
  95.         ret[0] = cols + rows;
  96.         for(int i = 0; i < a.size(); i++)
  97.         {
  98.             ret[2*i+1] = a.get(i);
  99.             ret[2*i+2] = b.get(i);
  100.         }
  101.         return ret;
  102.     }
  103. }
  104.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:7: error: class TopologicalOrdering is public, should be declared in a file named TopologicalOrdering.java
public class TopologicalOrdering {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/8HIUFh
language:
Java (12.0.1)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!