code: /*
   * Copyright (c) 2017, Hisao Tamaki and Keitaro Makii
  */
  
  package tw.heuristic;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  
  
  
  public class SafeSeparator {
    private static int MAX_MISSINGS = 100;
    private static int DEFAULT_MAX_STEPS = 10000;
    private static final boolean CONFIRM_MINOR = true;
  //  private static final boolean CONFIRM_MINOR = false;
  //    private static final boolean DEBUG = true;
    private static final boolean DEBUG = false;
  
    Graph g;
  
    int maxSteps;
    int steps;
    LeftNode[] leftNodes;
    ArrayList<RightNode> rightNodeList;
    ArrayList<MissingEdge> missingEdgeList;
    VertexSet available;
  
    public SafeSeparator (Graph g) {
      this.g = g;
    }
  
    public boolean isOneWaySafe(VertexSet separator, VertexSet component) {
      return isOneWaySafe(separator, component, DEFAULT_MAX_STEPS);
    }
  
    public boolean isOneWaySafe(VertexSet separator, VertexSet component, int maxSteps) {
      try {
        return isOneWaySafeCounting(separator, component, maxSteps);
      }
      catch (StepsExceededException e) {
        return false;
      }
    }
    public boolean isOneWaySafeCounting(VertexSet separator, VertexSet component, int maxSteps)
      throws StepsExceededException {
      //  System.out.println("isSafeSeparator " + separator);
      this.maxSteps = maxSteps;
      steps = 0;
      ArrayList<VertexSet> components = g.getComponents(separator);
      if (components.size() == 1) {
        //  System.err.println("non separator for safety testing:" + separator);
        //  throw new RuntimeException("non separator for safety testing:" + separator);
        return false;
      }
      if (countMissings(separator) > MAX_MISSINGS) {
        return false;
      }
      for (VertexSet compo: components) {
        if (compo.equals(component)) {
          continue;
        }
        VertexSet sep = g.neighborSet(compo);
        VertexSet rest = g.all.subtract(sep).subtract(compo);
        VertexSet[] contracts = findCliqueMinor(sep, rest);
        if (contracts == null) {
          return false;
        }
        if (CONFIRM_MINOR) {
          confirmCliqueMinor(sep, rest, contracts);
        }
      }
      return true;
    }
  
    private void addSteps(int s)
        throws StepsExceededException {
      steps += s;
      if (steps > maxSteps) {
        throw new StepsExceededException();
      }
    }
  
    public int decideSafeness(VertexSet separator) {
      return decideSafeness(separator, DEFAULT_MAX_STEPS);
    }
  
    public int decideSafeness(VertexSet separator, int maxSteps) {
      try {
        boolean b = isSafeSeparatorCounting(separator, maxSteps);
        if (b) {
          return steps + 1;
        }
        else {
          return -(steps + 1);
        }
      } catch (StepsExceededException e) {
        return -(steps + 1);
      }
    }
  
    public boolean isSafeSeparator(VertexSet separator) {
      return isSafeSeparator(separator, DEFAULT_MAX_STEPS);
    }
  
    public boolean isSafeSeparator(VertexSet separator, int maxSteps) {
      try {
        return isSafeSeparatorCounting(separator, maxSteps);
      } catch (StepsExceededException e) {
        return false;
      }
    }
  
    public boolean isSafeSeparatorCounting(VertexSet separator, int maxSteps)
      throws StepsExceededException {
      //  System.out.println("isSafeSeparator " + separator);
      this.maxSteps = maxSteps;
      steps = 0;
      if(separator.cardinality() <= 2){
        return true;
      }
      if(separator.cardinality() == 3){
        int first = separator.nextSetBit(0);
        VertexSet s = g.neighborSet[first];
        if(s.intersects(separator)){
          return true;
        }
      }
      ArrayList<VertexSet> components = g.getComponents(separator);
      if (components.size() == 1) {
        //  System.err.println("non separator for safety testing:" + separator);
        //  throw new RuntimeException("non separator for safety testing:" + separator);
        return false;
      }
      if (countMissings(separator) > MAX_MISSINGS) {
        return false;
      }
      for (VertexSet compo: components) {
        VertexSet sep = g.neighborSet(compo);
        VertexSet rest = g.all.subtract(sep).subtract(compo);
        VertexSet[] contracts = findCliqueMinor(sep, rest);
        if (contracts == null) {
          return false;
        }
        if (CONFIRM_MINOR) {
          confirmCliqueMinor(sep, rest, contracts);
        }
      }
      return true;
    }
  
    private class LeftNode {
      int index;
      int vertex;
      //    ArrayList<RightNode> rightNeighborList;
      //    VertexSet rightNeighborSet;
  
      LeftNode(int index, int vertex) {
        this.index = index;
        this.vertex = vertex;
        //      rightNeighborList = new ArrayList<>();
      }
  
      public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("left" + index + "(" + vertex + "):");
        sb.append(", " + g.neighborSet[vertex]);
        return sb.toString();
      }
    }
  
    private class RightNode {
      int index;
      VertexSet vertexSet;
      VertexSet neighborSet;
      LeftNode assignedTo;
      boolean printed;
  
      RightNode(int vertex) {
        vertexSet = new VertexSet(g.n);
        vertexSet.set(vertex);
        neighborSet = g.neighborSet(vertexSet);
      }
  
      RightNode(VertexSet vertexSet) {
        this.vertexSet = vertexSet;
        neighborSet = g.neighborSet(vertexSet);
      }
  
      boolean potentiallyCovers(MissingEdge me) {
        return
            assignedTo == null &&
            neighborSet.get(me.left1.vertex) &&
            neighborSet.get(me.left2.vertex);
      }
  
      boolean finallyCovers(MissingEdge me) {
        return
            assignedTo == me.left1 &&
            neighborSet.get(me.left2.vertex) ||
            assignedTo == me.left2 &&
            neighborSet.get(me.left1.vertex);
      }
  
      public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("right" + index + ":" + vertexSet);
        if (!printed) {
          sb.append(", " + neighborSet);
        }
        if (assignedTo != null) {
          sb.append("-> l" + assignedTo.index);
        }
        sb.append(", coveres {");
        for (MissingEdge me: missingEdgeList) {
          if (this.potentiallyCovers(me)) {
            sb.append("me" + me.index + " ");
          }
        }
        printed = true;
        sb.append("}");
  
        return sb.toString();
      }
  
    }
  
    private class MissingEdge {
      int index;
      LeftNode left1;
      LeftNode left2;
      boolean unAugmentable;
  
      MissingEdge(LeftNode left1, LeftNode left2) {
        this.left1 = left1;
        this.left2 = left2;
      }
  
      RightNode[] findCoveringPair()
          throws StepsExceededException {
        for (RightNode rn1: rightNodeList) {
          if (rn1.neighborSet.get(left1.vertex) &&
              !rn1.neighborSet.get(left2.vertex)) {
            for (RightNode rn2: rightNodeList) {
              if (!rn2.neighborSet.get(left1.vertex) &&
                  rn2.neighborSet.get(left2.vertex) &&
                  connectable(rn1.vertexSet, rn2.vertexSet)) {
                return new RightNode[]{rn1, rn2};
              }
            }
          }
        }
        return null;
      }
  
      boolean isFinallyCovered()
          throws StepsExceededException {
        for (RightNode rn: rightNodeList) {
          if (rn.finallyCovers(this)) {
            return true;
          }
        }
        return false;
      }
  
      public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("missing(" + left1.index + "," +
            left2.index + "), covered by {");
        for (RightNode rn: rightNodeList) {
          if (rn.potentiallyCovers(this)) {
            sb.append("r" + rn.index + " ");
          }
        }
        sb.append("}");
        return sb.toString();
      }
    }
    private VertexSet[] findCliqueMinor(VertexSet separator, VertexSet rest)
        throws StepsExceededException {
      int k = separator.cardinality();
      available = (VertexSet) rest.clone();
      leftNodes = new LeftNode[k];
      {
        int i = 0;
        for (int v = separator.nextSetBit(0); v >= 0;
            v = separator.nextSetBit(v + 1)) {
          leftNodes[i] = new LeftNode(i, v);
          i++;
        }
      }
  
      missingEdgeList = new ArrayList<>();
      {
        int i = 0;
        for (int v = separator.nextSetBit(0); v >= 0;
            v = separator.nextSetBit(v + 1)) {
          int j = i + 1;
          for (int w = separator.nextSetBit(v + 1); w >= 0;
              w = separator.nextSetBit(w + 1)) {
            if (!g.neighborSet[v].get(w)) {
              missingEdgeList.add(new MissingEdge(leftNodes[i], leftNodes[j]));
            }
            j++;
          }
          i++;
        }
      }
  
      int m = missingEdgeList.size();
  
      VertexSet[] result = new VertexSet[k];
      for (int i = 0; i < k; i++) {
        result[i] = new VertexSet(g.n);
        result[i].set(leftNodes[i].vertex);
      }
  
      if (m == 0) {
        return result;
      }
  
  //    System.out.println(m + " missings for separator size " + k +
  //        " and total components size " + rest.cardinality());
      for (int i = 0; i < m; i++) {
        missingEdgeList.get(i).index = i;
      }
  
      rightNodeList = new ArrayList<>();
      VertexSet ns = g.neighborSet(separator);
      ns.and(rest);
  
      for (int v = ns.nextSetBit(0); v >= 0;
          v = ns.nextSetBit(v + 1)) {
        if (g.neighborSet[v].cardinality() == 1) {
          continue;
        }
        boolean useless = true;
        for (MissingEdge me: missingEdgeList) {
          if (g.neighborSet[v].get(me.left1.vertex) ||
              g.neighborSet[v].get(me.left2.vertex)) {
            useless = false;
          }
        }
        if (useless) {
          continue;
        }
        RightNode rn = new RightNode(v);
        rightNodeList.add(rn);
        available.clear(v);
      }
  
      while (true) {
  
        MissingEdge zc = zeroCovered();
        if (zc == null) {
          break;
        }
        RightNode[] coveringPair = zc.findCoveringPair();
        if (coveringPair != null) {
          mergeRightNodes(coveringPair);
        }
        else {
          return null;
        }
      }
  
      boolean moving = true;
      while (rightNodeList.size() > k/2 && moving) {
        steps++;
        if (steps > maxSteps) {
          return null;
        }
        moving = false;
        MissingEdge lc = leastCovered();
        if (lc == null) {
          break;
        }
        RightNode[] coveringPair = lc.findCoveringPair();
        if (coveringPair != null) {
          mergeRightNodes(coveringPair);
          moving = true;
        }
        else {
          lc.unAugmentable = true;
        }
      }
  
      ArrayList<RightNode> temp = rightNodeList;
      rightNodeList = new ArrayList<>();
  
      for (RightNode rn: temp) {
        boolean covers = false;
        for (MissingEdge me: missingEdgeList) {
          if (rn.potentiallyCovers(me)) {
            covers = true;
            break;
          }
        }
        if (covers) {
          rightNodeList.add(rn);
        }
      }
  
      int nRight = rightNodeList.size();
      for (int i = 0; i < nRight; i++) {
        rightNodeList.get(i).index = i;
      }
  
      if (DEBUG) {
        System.out.println(k + " lefts");
        for (LeftNode ln: leftNodes) {
          System.out.println(ln);
        }
        System.out.println(nRight + " rights");
        for (RightNode rn: rightNodeList) {
          System.out.println(rn);
        }
        System.out.println(m + " missings");
        for (MissingEdge me: missingEdgeList) {
          System.out.println(me);
        }
      }
  
      while (!missingEdgeList.isEmpty()) {
        if (DEBUG) {
          System.out.println(missingEdgeList.size() + " missings");
          for (RightNode rn: rightNodeList) {
            System.out.println(rn);
          }
        }
        int[] bestPair = null;
        int maxMinCover = 0;
        int maxFc = 0;
  
        for (LeftNode ln: leftNodes) {
          for (RightNode rn: rightNodeList) {
            if (rn.assignedTo != null ||
                !rn.neighborSet.get(ln.vertex)) {
              continue;
            }
            rn.assignedTo = ln;
            int minCover = minCover();
            int fc = 0;
            for (MissingEdge me: missingEdgeList) {
              if (me.isFinallyCovered()) {
                fc++;
              }
            }
            rn.assignedTo = null;
            if (bestPair == null || minCover > maxMinCover) {
              maxMinCover = minCover;
              bestPair = new int[] {ln.index, rn.index};
              maxFc = fc;
            }
            else if (minCover == maxMinCover && fc > maxFc) {
              bestPair = new int[] {ln.index, rn.index};
              maxFc = fc;
            }
          }
        }
        if (maxMinCover == 0) {
          return null;
        }
  
        if (DEBUG) {
          System.out.println("maxMinCover = " + maxMinCover +
              ", maxFC = " + maxFc +
              ", bestPair = " + Arrays.toString(bestPair));
  
        }
        rightNodeList.get(bestPair[1]).assignedTo =
            leftNodes[bestPair[0]];
  
        ArrayList<MissingEdge> temp1 = missingEdgeList;
        missingEdgeList = new ArrayList<>();
        for (MissingEdge me: temp1) {
          if (!me.isFinallyCovered()) {
            missingEdgeList.add(me);
          }
        }
      }
  
      if (DEBUG) {
        System.out.println("assignment success");
        for (RightNode rn: rightNodeList) {
          System.out.println(rn);
        }
      }
  
      for (RightNode rn: rightNodeList) {
        if (rn.assignedTo != null) {
          int i = rn.assignedTo.index;
          result[i].or(rn.vertexSet);
        }
      }
      return result;
    }
  
    void confirmCliqueMinor(VertexSet separator, VertexSet rest, VertexSet[] contracts) {
      {
        int i = 0;
        for (int v = separator.nextSetBit(0); v >= 0;
            v = separator.nextSetBit(v + 1)) {
          if (!contracts[i].get(v)) {
            throw new RuntimeException("Not a clique minor: vertex " + v +
                " is not contained in the contracted " + contracts[i]);
          }
          i++;
        }
      }
      for (int i = 0; i < contracts.length; i++) {
        for (int j = i + 1; j < contracts.length; j++) {
          if (contracts[i].intersects(contracts[j])) {
            throw new RuntimeException("Not a clique minor: contracts " +
                contracts[i] + " and " + contracts[j] + " intersect with each other");
          }
          if (!g.neighborSet(contracts[i]).intersects(contracts[j])) {
            throw new RuntimeException("Not a clique minor: contracts " +
                contracts[i] + " and " + contracts[j] + " are not adjacent to each other");
          }
        }
      }
  
      for (int i = 0; i < contracts.length; i++) {
        if (!g.isConnected(contracts[i])) {
          throw new RuntimeException("Not a clique minor: contracted " +
              contracts[i] + " is not connected");
        }
      }
    }
  
    int minCover() throws StepsExceededException {
      int minCover = g.n;
      for (MissingEdge me: missingEdgeList) {
        if (me.isFinallyCovered()) {
          continue;
        }
        int nCover = 0;
        addSteps(1);
        for (RightNode rn: rightNodeList) {
          if (rn.potentiallyCovers(me)) {
            nCover++;
          }
        }
        if (nCover < minCover) {
          minCover = nCover;
        }
      }
      return minCover;
    }
  
    MissingEdge leastCovered() throws StepsExceededException {
      int minCover = 0;
      MissingEdge result = null;
      for (MissingEdge me: missingEdgeList) {
        if (me.unAugmentable) {
          continue;
        }
        int nCover = 0;
        addSteps(1);
        for (RightNode rn: rightNodeList) {
          if (rn.potentiallyCovers(me)) {
            nCover++;
          }
        }
        if (result == null || nCover < minCover) {
          minCover = nCover;
          result =  me;
        }
      }
      return result;
    }
  
    MissingEdge zeroCovered() throws StepsExceededException {
      for (MissingEdge me: missingEdgeList) {
        int nCover = 0;
        addSteps(1);
        for (RightNode rn: rightNodeList) {
          if (rn.potentiallyCovers(me)) {
            nCover++;
          }
        }
        if (nCover == 0) {
          return me;
        }
      }
      return null;
    }
  
    boolean connectable(VertexSet vs1, VertexSet vs2)
        throws StepsExceededException {
      VertexSet vs = (VertexSet) vs1.clone();
      while (true) {
        addSteps(1);
        VertexSet ns = g.neighborSet(vs);
        if (ns.intersects(vs2)) {
          return true;
        }
        ns.and(available);
        if (ns.isEmpty()) {
          return false;
        }
        vs.or(ns);
      }
    }
  
    void mergeRightNodes(RightNode[] coveringPair) {
      RightNode rn1 = coveringPair[0];
      RightNode rn2 = coveringPair[1];
  
      VertexSet connected = connect(rn1.vertexSet, rn2.vertexSet);
      RightNode rn = new RightNode(connected);
      rightNodeList.remove(rn1);
      rightNodeList.remove(rn2);
      rightNodeList.add(rn);
    }
  
    VertexSet connect(VertexSet vs1, VertexSet vs2) {
      ArrayList<VertexSet> layerList = new ArrayList<>();
  
      VertexSet vs = (VertexSet) vs1.clone();
      while (true) {
        VertexSet ns = g.neighborSet(vs);
        if (ns.intersects(vs2)) {
          break;
        }
        ns.and(available);
        layerList.add(ns);
        vs.or(ns);
      }
  
      VertexSet result = vs1.unionWith(vs2);
  
      VertexSet back = g.neighborSet(vs2);
      for (int i = layerList.size() - 1; i >= 0; i--) {
        VertexSet ns = layerList.get(i);
        ns.and(back);
        int v = ns.nextSetBit(0);
        result.set(v);
        available.clear(v);
        back = g.neighborSet[v];
      }
      return result;
    }
  
    int countMissings(VertexSet s) {
      int count = 0;
      for (int v = s.nextSetBit(0); v >= 0;
          v = s.nextSetBit(v + 1)) {
        count += s.subtract(g.neighborSet[v]).cardinality() - 1;
      }
      return count / 2;
    }
  
    private static class StepsExceededException extends Exception {
    }
  }
  