CareerCup

If the bridges are modeled as edges of a graph, the question seem to be essentially asking for a graph planarity testing algorithm.

It is a problem that can be solved using greedy technique.
Algorithm:
1: Sort the set of bridges in descending order of their no of intersection. (high intersecting at top).
2: Check if there exist an intersection in the current set of bridges.
3: If intersection exists:
3.1 Remove the top bridge.
3.2 Go to step 2
4: If intersection doesn't exits we are done. Return the set of bridges or count.

Here we try to find the number of bridges we can retain without causing an intersection.

Model the bridges as nodes in a graph and intersections as edges between nodes.

Now, we try to build a new graph adding nodes to an empty graph. At each step, we have choice of adding or not adding a node from the original graph to the new graph.

Tested this with some test sets. Looks like working. Please let me know if it fails for a case.

public class Graph2 {

	// the adjacency matrix
	int[][] matrix;

	// number of nodes in the graph
	int numNodes;

	public Graph2(int[][] pmatrix, int nodes) {
		matrix = pmatrix;
		numNodes = nodes;
	}

	/**
	 * Find the maximum number of nodes that can be added to a new graph from
	 * this graph such that the new graph is completely disconnected (has no
	 * edges in it)
	 * 
	 * @param nodeToCheck
	 *            The node that has to be processed now
	 * @param newGraphNodes
	 *            Array of nodes that has been added in the new graph
	 * @return The max number of nodes that can be added without having any
	 *         edges in the graph
	 */
	int maxNodes(int nodeToCheck, int[] newGraphNodes) {

		/* check if the new graph has an edge */
		if (isIntersecting(newGraphNodes)) {
			return -1;
		}

		/* check if there is an unprocessed node */
		if (nodeToCheck < 0) {
			return 1;
		}

		/* create a new array and copy the content. can't use clone here */
		int na1[] = new int[newGraphNodes.length + 1];
		System.arraycopy(newGraphNodes, 0, na1, 0, newGraphNodes.length);

		/* append the node to be processed to this array */
		na1[na1.length - 1] = nodeToCheck;

		/*
		 * this checks the max nodes possible to obtain by adding the current
		 * node under process
		 */
		int l1 = 1 + maxNodes(nodeToCheck - 1, na1);

		/*
		 * this checks the max nodes possible to obtain by leaving out the
		 * current node under process
		 */
		int[] na2 = newGraphNodes.clone();
		int l2 = maxNodes(nodeToCheck - 1, na2);

		if (l1 > l2) {
			return l1;
		} else {
			return l2;
		}
	}

	boolean isIntersecting(int[] nodes) {
		int lastAddedNode = numNodes - nodes.length;
		for (int i = numNodes - 1; i > lastAddedNode; i--) {
			if (matrix[i][lastAddedNode] == 1) {
				return true;

			}
		}
		return false;
	}

	public static void main(String[] args) {

		int m[][] = { { 0, 1, 0, 0, 0, 0, 0, 0, 0 },
				{ 1, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 1, 0, 0, 0 },
				{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 0, 0, 1, 0, 0, 0, 0, 0, 1 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 1, 0, 0, 0 } };

		Graph2 test = new Graph2(m, 9);

		int na[] = new int[0];
		int l = test.maxNodes(8, na);

		System.out.println("Min number of bridges to remove: "
				+ (test.numNodes - l));
	}
}