code: import java.util.HashMap;
  import java.util.HashSet;
  import java.util.Map;
  import java.util.Map.Entry;
  import java.util.Set;
  
  public class ConsistencyGraph {
  	private Map<Integer, Set<Integer>> edges;
  	private APTA apta;
  	Map<Integer, Triple> merged = new HashMap<>();
  	Map<Integer, Triple> mergedInit = new HashMap<>();
  	private Set<Integer> acceptableClique;
  	private Set<Integer> rejectableClique;
  
  	public ConsistencyGraph(APTA apta, boolean noisyMode) {
  		edges = new HashMap<>();
  		this.apta = apta;
  
  		if (!noisyMode) {
  			for (int i = 0; i < apta.getSize(); i++) {
  				edges.put(i, new HashSet<Integer>());
  			}
  			Set<Integer> acceptableNodes = apta.getAcceptableNodes();
  			Set<Integer> rejectableNodes = apta.getRejectableNodes();
  
  			for (int i : acceptableNodes) {
  				for (int j : rejectableNodes) {
  					edges.get(i).add(j);
  					edges.get(j).add(i);
  				}
  			}
  
  			for (int i = 0; i < apta.getSize(); i++) {
  				mergedInit.put(i,
  						new Triple(i, apta.isAcceptable(i), apta.isRejectable(i)));
  			}
  
  			findConsistentEdges(apta.getRoot());
  		}
  	}
  
  	public Map<Integer, Set<Integer>> getEdges() {
  		return edges;
  	}
  
  	private void findConsistentEdges(Node node) {
  		int thisNumber = node.getNumber();
  		for (Entry<String, Node> entry : node.getChildren().entrySet()) {
  			findConsistentEdges(entry.getValue());
  		}
  		// for (Entry<String, Node> entry : node.getChildren().entrySet()) {
  		// String label = entry.getKey();
  		// Node child = entry.getValue();
  		// int childNumber = child.getNumber();
  		// boolean isAcceptable = apta.isAcceptable(thisNumber);
  		// boolean isRejectable = apta.isRejectable(thisNumber);
  		// Set<Integer> inequalityWithChild = new HashSet<>(
  		// edges.get(childNumber));
  		// for (int i : inequalityWithChild) {
  		// Node compareWith = apta.getNode(i);
  		// Node parent = compareWith.getParent(label);
  		// if (compareWith.getNumber() != childNumber
  		// && edges.get(childNumber).contains(
  		// compareWith.getNumber()) && parent != null) {
  		// edges.get(thisNumber).add(parent.getNumber());
  		// edges.get(parent.getNumber()).add(thisNumber);
  		// }
  		// }
  		// Set<Integer> buffer = new HashSet<>();
  		// buffer.add(childNumber);
  		// boolean isInequality = false;
  		// while (child.getChildren().containsKey(label)) {
  		// child = child.getChildren().get(label);
  		// childNumber = child.getNumber();
  		// if (isAcceptable != apta.isAcceptable(childNumber)
  		// && isRejectable != apta.isRejectable(childNumber)) {
  		// buffer.add(childNumber);
  		// isInequality = true;
  		// }
  		// }
  		// if (isInequality) {
  		// for (int number : buffer) {
  		// edges.get(thisNumber).add(number);
  		// edges.get(number).add(thisNumber);
  		// }
  		// }
  		// }
  
  		for (int otherNumber = thisNumber + 1; otherNumber < apta.getSize(); otherNumber++) {
  			if (otherNumber != thisNumber) {
  				Node other = apta.getNode(otherNumber);
  				if (other.isAcceptable() != node.isAcceptable()
  						&& other.isRejectable() != node.isRejectable()) {
  					// I added this pair when initialized edges[][]
  					continue;
  				}
  				merged = new HashMap<>(mergedInit);
  				if (!testMerge(node, other)) {
  					edges.get(thisNumber).add(otherNumber);
  					edges.get(otherNumber).add(thisNumber);
  				}
  			}
  		}
  	}
  
  	// node number < other number
  	private boolean testMerge(Node node, Node other) {
  		Triple nodeRep = merged.get(node.getNumber());
  		while (nodeRep != merged.get(nodeRep.num)) {
  			nodeRep = merged.get(nodeRep.num);
  		}
  		Triple otherRep = merged.get(other.getNumber());
  		while (otherRep != merged.get(otherRep.num)) {
  			otherRep = merged.get(otherRep.num);
  		}
  		if (nodeRep.isAcc != otherRep.isAcc && nodeRep.isRej != otherRep.isRej) {
  			return false;
  		}
  		Triple newRep = new Triple(Math.min(nodeRep.num, otherRep.num),
  				nodeRep.isAcc || otherRep.isAcc,
  				nodeRep.isRej || otherRep.isRej);
  		merged.put(nodeRep.num, newRep);
  		merged.put(node.getNumber(), newRep);
  		merged.put(otherRep.num, newRep);
  		merged.put(other.getNumber(), newRep);
  		for (String label : node.getChildren().keySet()) {
  			if (other.getChildren().containsKey(label)) {
  				if (!testMerge(node.getChild(label), other.getChild(label))) {
  					return false;
  				}
  			}
  		}
  		return true;
  	}
  
  	private class Triple {
  		int num;
  		boolean isAcc;
  		boolean isRej;
  
  		public Triple(int num, boolean isAcc, boolean isRej) {
  			this.num = num;
  			this.isAcc = isAcc;
  			this.isRej = isRej;
  		}
  	}
  
  	public void findClique() {
  		int maxDegree = 0;
  		int maxV = -1;
  		acceptableClique = new HashSet<>();
  		for (int candidate : apta.getAcceptableNodes()) {
  			int candidateDegree = getEdges().get(candidate).size();
  			if (candidateDegree > maxDegree) {
  				maxDegree = candidateDegree;
  				maxV = candidate;
  			}
  		}
  		int last = maxV;
  		if (last != -1) {
  			acceptableClique.add(last);
  			int anotherOne = findNeighbourWithHighestDegree(
  					acceptableClique, last, true);
  			while (anotherOne != -1) {
  				acceptableClique.add(anotherOne);
  				last = anotherOne;
  				anotherOne = findNeighbourWithHighestDegree(
  						acceptableClique, last, true);
  				if (last == anotherOne) {
  					break;
  				}
  			}
  		}
  
  		maxDegree = 0;
  		maxV = -1;
  		rejectableClique = new HashSet<>();
  		for (int candidate : apta.getRejectableNodes()) {
  			int candidateDegree = getEdges().get(candidate).size();
  			if (candidateDegree > maxDegree) {
  				maxDegree = candidateDegree;
  				maxV = candidate;
  			}
  		}
  		last = maxV;
  		if (last != -1) {
  			rejectableClique.add(last);
  			int anotherOne = findNeighbourWithHighestDegree(
  					rejectableClique, last, false);
  			while (anotherOne != -1) {
  				rejectableClique.add(anotherOne);
  				last = anotherOne;
  				anotherOne = findNeighbourWithHighestDegree(
  						rejectableClique, last, false);
  				if (last == anotherOne) {
  					break;
  				}
  			}
  		}
  	}
  
  	private int findNeighbourWithHighestDegree(Set<Integer> cur, int v, boolean acceptable) {
  		int maxDegree = 0;
  		int maxNeighbour = -1;
  		// uv - edge
  		for (int u : getEdges().get(v)) {
  			if (acceptable && !apta.isAcceptable(u)) {
  				continue;
  			}
  			if (!acceptable && !apta.isRejectable(u)) {
  				continue;
  			}
  			boolean uInClique = true;
  			// check if other vertices in cur connected with u
  			for (int w : cur) {
  				if (w != v) {
  					if (!getEdges().get(w).contains(u)) {
  						uInClique = false;
  						break;
  					}
  				}
  			}
  			if (uInClique) {
  				int uDegree = getEdges().get(u).size();
  				if (uDegree > maxDegree) {
  					maxDegree = uDegree;
  					maxNeighbour = u;
  				}
  			}
  		}
  		return maxNeighbour;
  	}
  
  	public Set<Integer> getAcceptableClique() {
  		return acceptableClique;
  	}
  
  	public Set<Integer> getRejectableClique() {
  		return rejectableClique;
  	}
  
  	public int getCliqueSize() {
  		return acceptableClique.size() + rejectableClique.size();
  	}
  }
  