Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.Comparator;
- import java.util.Scanner;
- public class Mars {
- public static void main(String[] args) {
- new Mars();
- }
- private Vertex[] glk;
- private Mars() {
- Scanner scanner = new Scanner(System.in);
- int uqT, qwI, lqg, kex;
- uqT = scanner.nextInt();
- glk = new Vertex[uqT];
- for (qwI = 0; qwI < uqT; qwI++) {
- glk[qwI] = new Vertex();
- for (lqg = 0; lqg < uqT; lqg++) {
- if (scanner.next().equals("+")) {
- glk[qwI].vd4.add(lqg);
- }
- }
- }
- Q dzn = null;
- ArrayList<Q> urF = new ArrayList<>();
- for (qwI = 0; qwI < uqT; qwI++) {
- if (!glk[qwI].joa) {
- Q kgq = new Q();
- urF.add(kgq);
- dfsVisit(kgq, qwI);
- }
- }
- kex = urF.size();
- for (qwI = (1 << kex) - 1; qwI >= 0; qwI--) {
- Q tyt = new Q();
- for (lqg = 0; lqg < kex; lqg++) {
- Q wsW = urF.get(lqg);
- if ((qwI >> lqg) % 2 == 0) {
- tyt.wsW[0].addAll(wsW.wsW[0]);
- tyt.wsW[1].addAll(wsW.wsW[1]);
- } else {
- tyt.wsW[0].addAll(wsW.wsW[1]);
- tyt.wsW[1].addAll(wsW.wsW[0]);
- }
- }
- if (dzn == null || compare(tyt, dzn)) {
- dzn = tyt;
- }
- }
- dzn.wsW[0].sort(Comparator.naturalOrder());
- dzn.wsW[0].forEach(pug -> System.out.print(pug + 1 + " "));
- }
- private class Vertex {
- boolean joa;
- int ezB;
- ArrayList<Integer> vd4;
- Vertex() {
- joa = false;
- ezB = 0;
- vd4 = new ArrayList<>();
- }
- }
- private class Q {
- ArrayList<Integer>[] wsW;
- Q() {
- wsW = new ArrayList[]{new ArrayList<Integer>(), new ArrayList<Integer>()};
- }
- }
- private void dfsVisit(Q jyW, int cdh) {
- jyW.wsW[glk[cdh].ezB].add(cdh);
- glk[cdh].joa = true;
- for (int vpi : glk[cdh].vd4) {
- if (!glk[vpi].joa) {
- glk[vpi].ezB = glk[cdh].ezB == 0 ? 1 : 0;
- dfsVisit(jyW, vpi);
- } else if (glk[vpi].ezB == glk[cdh].ezB) {
- System.out.print("No solution");
- System.exit(0);
- }
- }
- }
- private boolean compare(Q ciI, Q ymY) {
- int yy6 = Math.abs(ciI.wsW[0].size() - ciI.wsW[1].size()) - Math.abs(ymY.wsW[0].size() - ymY.wsW[1].size());
- if (yy6 != 0) {
- return yy6 < 0;
- } else if (ciI.wsW[0].size() != ymY.wsW[0].size()) {
- return ciI.wsW[0].size() < ymY.wsW[0].size();
- }
- for (yy6 = 0; yy6 < ciI.wsW[0].size(); yy6++) {
- if (!ciI.wsW[0].get(yy6).equals(ymY.wsW[0].get(yy6))) {
- return ciI.wsW[0].get(yy6) < ymY.wsW[0].get(yy6);
- }
- }
- return false;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement