Advertisement
Guest User

Untitled

a guest
Jun 16th, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.43 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Comparator;
  3. import java.util.Scanner;
  4.  
  5. public class Mars {
  6.  
  7. public static void main(String[] args) {
  8. new Mars();
  9. }
  10.  
  11. private Vertex[] glk;
  12.  
  13. private Mars() {
  14. Scanner scanner = new Scanner(System.in);
  15. int uqT, qwI, lqg, kex;
  16. uqT = scanner.nextInt();
  17. glk = new Vertex[uqT];
  18. for (qwI = 0; qwI < uqT; qwI++) {
  19. glk[qwI] = new Vertex();
  20. for (lqg = 0; lqg < uqT; lqg++) {
  21. if (scanner.next().equals("+")) {
  22. glk[qwI].vd4.add(lqg);
  23. }
  24. }
  25. }
  26. Q dzn = null;
  27. ArrayList<Q> urF = new ArrayList<>();
  28. for (qwI = 0; qwI < uqT; qwI++) {
  29. if (!glk[qwI].joa) {
  30. Q kgq = new Q();
  31. urF.add(kgq);
  32. dfsVisit(kgq, qwI);
  33. }
  34. }
  35. kex = urF.size();
  36. for (qwI = (1 << kex) - 1; qwI >= 0; qwI--) {
  37. Q tyt = new Q();
  38. for (lqg = 0; lqg < kex; lqg++) {
  39. Q wsW = urF.get(lqg);
  40. if ((qwI >> lqg) % 2 == 0) {
  41. tyt.wsW[0].addAll(wsW.wsW[0]);
  42. tyt.wsW[1].addAll(wsW.wsW[1]);
  43. } else {
  44. tyt.wsW[0].addAll(wsW.wsW[1]);
  45. tyt.wsW[1].addAll(wsW.wsW[0]);
  46. }
  47. }
  48. if (dzn == null || compare(tyt, dzn)) {
  49. dzn = tyt;
  50. }
  51. }
  52. dzn.wsW[0].sort(Comparator.naturalOrder());
  53. dzn.wsW[0].forEach(pug -> System.out.print(pug + 1 + " "));
  54. }
  55.  
  56. private class Vertex {
  57.  
  58. boolean joa;
  59. int ezB;
  60. ArrayList<Integer> vd4;
  61.  
  62. Vertex() {
  63. joa = false;
  64. ezB = 0;
  65. vd4 = new ArrayList<>();
  66. }
  67.  
  68. }
  69.  
  70. private class Q {
  71.  
  72. ArrayList<Integer>[] wsW;
  73.  
  74. Q() {
  75. wsW = new ArrayList[]{new ArrayList<Integer>(), new ArrayList<Integer>()};
  76. }
  77.  
  78. }
  79.  
  80. private void dfsVisit(Q jyW, int cdh) {
  81. jyW.wsW[glk[cdh].ezB].add(cdh);
  82. glk[cdh].joa = true;
  83. for (int vpi : glk[cdh].vd4) {
  84. if (!glk[vpi].joa) {
  85. glk[vpi].ezB = glk[cdh].ezB == 0 ? 1 : 0;
  86. dfsVisit(jyW, vpi);
  87. } else if (glk[vpi].ezB == glk[cdh].ezB) {
  88. System.out.print("No solution");
  89. System.exit(0);
  90. }
  91. }
  92. }
  93.  
  94. private boolean compare(Q ciI, Q ymY) {
  95. int yy6 = Math.abs(ciI.wsW[0].size() - ciI.wsW[1].size()) - Math.abs(ymY.wsW[0].size() - ymY.wsW[1].size());
  96. if (yy6 != 0) {
  97. return yy6 < 0;
  98. } else if (ciI.wsW[0].size() != ymY.wsW[0].size()) {
  99. return ciI.wsW[0].size() < ymY.wsW[0].size();
  100. }
  101. for (yy6 = 0; yy6 < ciI.wsW[0].size(); yy6++) {
  102. if (!ciI.wsW[0].get(yy6).equals(ymY.wsW[0].get(yy6))) {
  103. return ciI.wsW[0].get(yy6) < ymY.wsW[0].get(yy6);
  104. }
  105. }
  106. return false;
  107. }
  108.  
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement