fork(2) download
copy 
  1. #include <functional>
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. /**
  7.  * Checks if node is adj to all nodes in subgraph.
  8.  *
  9.  * @param node      the node to check for adjacency all other nodes in the subgraph
  10.  * @param subgraph  an array of node integers
  11.  * @param len       the length of the subgraph array
  12.  * @param adj       a function accepting two integers corresponding to nodes and returns 
  13.  *                  whether they are adjacent
  14.  * @returns         whether node is adjacent to all nodes in subgraph.
  15.  */ 
  16. inline bool adj_all(int node, int* subgraph, int len, const function<bool(int, int)> &adj){
  17. 	for(int i = 0;i < len;i++){
  18. 		//cout << "Comparing with " << nodes[chain[i]] << "." << endl;
  19. 		if(i == node || !adj(subgraph[i], node)) {
  20. 			return false;
  21. 		}
  22. 	}
  23. 	return true;
  24. }
  25.  
  26. /**
  27.  * Finds the size of the maximal clique in the graph.
  28.  *
  29.  * @param num_nodes     the number of nodes
  30.  * @param adj           a function accepting two integers corresponding to nodes and returns 
  31.  *                      whether they are adjacent
  32.  * @returns the size of the maximal clique.
  33.  */
  34. int max_clique(int num_nodes, const function<bool(int, int)> &adj)
  35. {
  36. 	if(num_nodes <= 0)
  37. 		return 0;
  38.  
  39. 	// Holds indices into nodes of current clique. Permuted to check every subgraph.
  40. 	// The stack is kept in sorted order (solely by nature of how it is incremented/permuted) so
  41. 	// as to only check each subgraph once.
  42. 	int stack[num_nodes + 1];
  43. 	stack[0] = 0;
  44.  
  45. 	// Holds the current index in the stack to permute.
  46. 	int index = 0;
  47.  
  48. 	// Holds the size of the largest clique found.
  49. 	int max_len = 0;
  50.  
  51. 	while(index >= 0) {
  52. 		bool complete = true;
  53.  
  54. 		// Down the tree. Add new nodes to the stack while we can find a neighbor to the 
  55. 		// top node on the stack that is also adjacent to all nodes in the stack.
  56. 		while(complete) {
  57.  
  58. 			// Find a neighbor.
  59. 			complete = false; // This will stay false if no neighbor is found.
  60. 			for(int i = stack[index] + 1;!complete && i < num_nodes;i++) {
  61. 				if(adj_all(i, stack, index + 1, adj)) {
  62. 					stack[index + 1] = i; // Add this node to the stack.
  63. 					index++; // Advance the stack pointer.
  64. 					complete = true;
  65. 				}
  66. 			}
  67.  
  68. 		}
  69. 		complete = false;
  70.  
  71. 		if(index + 1 > max_len) {
  72. 			max_len = index + 1;
  73. 		}
  74.  
  75. 		while(!complete && index >= 0) {
  76. 			do {
  77. 				// If we get here, no suitable neighbor could be found for the top node on the 
  78. 				// stack.
  79. 				// So we will permute the last neighbor on the stack.
  80. 				stack[index]++;
  81. 				complete = adj_all(stack[index], stack, index, adj);
  82. 			} while(!complete && stack[index] < num_nodes);
  83.  
  84. 			if(stack[index] >= num_nodes) {
  85. 				// If we get here, we've tried all possibilities for top node on the stack and 
  86. 				// none of them were complete with the rest of the stack, so we need to pop the 
  87. 				// node off the stack and start permuting the node below it.
  88. 				index--; // Pop the stack.
  89.  
  90. 				stack[index]++;
  91. 				complete = adj_all(stack[index], stack, index, adj);
  92. 			}
  93. 		}
  94. 	}
  95.  
  96. 	return max_len;
  97. }
  98.  
  99. /**
  100.  * Whether two nodes are adjacent.
  101.  */
  102. bool adj1(int n1, int n2) {
  103.   static int connects[9][9] = {
  104.   {0,1,1,1,0,0,1,1,1},
  105.   {1,0,1,1,0,0,0,1,1},
  106.   {1,1,0,1,1,1,0,0,1},
  107.   {1,1,1,0,1,1,1,0,0},
  108.   {0,0,1,1,0,1,1,0,0},
  109.   {0,0,1,1,1,0,1,1,1},
  110.   {1,0,0,1,1,1,0,1,1},
  111.   {1,1,0,0,0,1,1,0,1},
  112.   {1,1,1,0,0,1,1,1,0}};
  113.  
  114.   return connects[n1][n2];
  115. }
  116.  
  117. /**
  118.  * Whether two nodes are adjacent.
  119.  */
  120. bool adj2(int n1, int n2) {
  121.   static int connects[23][23] = {
  122.   {0,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0},
  123.   {0,0,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1},
  124.   {1,1,0,0,1,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,0,1,0},
  125.   {0,1,0,0,1,1,0,1,1,1,0,0,0,1,1,1,1,1,1,1,1,0,1},
  126.   {1,1,1,1,0,1,1,0,1,1,1,0,0,0,1,1,1,1,1,1,1,1,0},
  127.   {0,1,1,1,1,0,1,1,0,1,1,1,0,1,1,1,0,0,1,1,1,1,1},
  128.   {1,0,1,0,1,1,0,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1},
  129.   {1,0,0,1,0,1,1,0,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1},
  130.   {1,0,0,1,1,0,1,1,0,1,1,0,1,1,1,0,1,1,1,1,1,1,1},
  131.   {1,1,0,1,1,1,0,1,1,0,1,1,0,1,1,1,0,1,0,1,1,1,1},
  132.   {1,1,1,0,1,1,1,0,1,1,0,1,1,0,1,1,1,0,0,0,1,1,1},
  133.   {1,1,1,0,0,1,1,1,0,1,1,0,1,1,0,1,1,1,0,0,1,1,1},
  134.   {1,1,1,0,0,0,1,1,1,0,1,1,0,1,1,0,1,1,1,0,1,1,1},
  135.   {1,1,1,1,0,1,0,1,1,1,0,1,1,0,1,1,0,1,1,1,0,1,1},
  136.   {1,1,1,1,1,1,1,0,1,1,1,0,1,1,0,1,1,0,1,1,0,0,1},
  137.   {1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,0,1,1,0,1,0,0,1},
  138.   {1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,0,1,1,0,1,0,1},
  139.   {1,1,1,1,1,0,0,1,1,1,0,1,1,1,0,1,1,0,1,1,1,1,0},
  140.   {0,1,1,1,1,1,1,1,1,0,0,0,1,1,1,0,1,1,0,1,1,1,1},
  141.   {1,0,1,1,1,1,1,1,1,1,0,0,0,1,1,1,0,1,1,0,0,1,0},
  142.   {0,1,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,0,0,1,1},
  143.   {1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,0,0},
  144.   {0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0}};
  145.  
  146.   return connects[n1][n2];
  147. }
  148.  
  149. /**
  150.  * Whether two nodes are adjacent.
  151.  */
  152. bool adj3(int n1, int n2) {
  153.   static int connects[41][41] = {
  154.   {0,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,0,1,1,1,1,1,1,1,1,0,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1},
  155.   {1,0,1,1,1,1,1,1,1,1,0,1,1,0,0,1,0,0,1,1,1,1,1,1,1,0,1,0,0,0,1,1,1,0,1,1,1,1,1,1,1},
  156.   {1,1,0,1,1,1,1,1,1,0,1,0,1,1,0,1,0,0,0,1,1,1,1,1,1,0,1,1,1,0,0,1,0,1,0,1,1,1,1,1,1},
  157.   {1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,0,0,0,1,1,1,1,1,1,0,1,1,1,0,0,1,0,1,0,1,1,1,1,1},
  158.   {1,1,1,1,0,1,1,1,1,0,1,0,1,1,1,0,1,1,0,0,0,1,1,1,1,1,0,0,1,1,1,0,0,1,0,1,0,1,1,1,1},
  159.   {1,1,1,1,1,0,1,1,1,1,0,1,0,1,1,0,0,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,1,0,1,0,1,1,1},
  160.   {1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,0,0,0,1,1,1,1,0,1,0,1,1,1,1,0,1,0,1,0,1,1},
  161.   {1,1,1,1,1,1,1,0,1,1,1,1,0,0,1,1,1,1,0,1,1,0,0,0,1,1,1,1,1,1,0,1,1,1,1,0,1,0,1,0,1},
  162.   {1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,0,0,0,1,1,1,0,1,1,0,1,1,1,1,0,1,0,1,0},
  163.   {0,1,0,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,0,1,1,0,1,1,1,1,1,1,0,1,1,1,0,0,1,1,1},
  164.   {1,0,1,0,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,0,1,1,0,1,1,1,1,1,1,0,1,1,1,0,0,1,1},
  165.   {1,1,0,1,0,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,0,1,0,0,1,1,1,1,1,1,0,1,1,1,0,0,1},
  166.   {1,1,1,0,1,0,1,0,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,0,0,0,1,1,1,1,0,1,1,0,1,1,1,0,0},
  167.   {0,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,0,1,0,1,1,0,1,0,0,0,1,1,1,1,0,0,0,1,1,0,1},
  168.   {1,0,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,0,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,0,1,1,0},
  169.   {0,1,1,1,0,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,0,1,0,1,0,0,0,1,1,0,1,1,1,1,1,1,0,0,0},
  170.   {0,0,0,1,1,0,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1},
  171.   {1,0,0,0,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,0,0,1,0,0,1,1,1,1,1,1,1},
  172.   {1,1,0,0,0,1,1,0,1,1,1,1,0,0,1,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,0,0,0,0,0,1,1,1,1,1,1},
  173.   {1,1,1,0,0,0,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,0,1,0,0,0,1,1,1,1,1},
  174.   {1,1,1,1,0,0,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,0,0,1,1,1,1},
  175.   {1,1,1,1,1,0,0,0,1,0,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,0,0,0,1,1,1},
  176.   {1,1,1,1,1,1,0,0,0,0,0,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,0,0,1,1,1,1,0,1,1,0,0,0,1,1},
  177.   {1,1,1,1,1,1,1,0,0,1,0,0,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,0,0,0,1},
  178.   {1,1,1,1,1,1,1,1,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,0,1,1,0,0,0},
  179.   {0,0,0,1,1,1,1,1,1,0,1,1,0,0,0,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,0,1,1,1,0},
  180.   {0,1,1,0,0,0,1,1,1,1,0,0,0,1,1,0,1,0,1,0,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,0,1},
  181.   {1,0,1,1,0,0,0,1,1,1,1,0,0,0,1,0,1,1,0,1,0,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,0},
  182.   {0,0,1,1,1,0,1,1,0,1,1,1,1,0,0,0,0,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,0,1,0,1,1,1},
  183.   {1,0,0,1,1,1,0,1,1,1,1,1,1,0,0,1,0,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,0,1,0,1,1},
  184.   {1,1,0,0,1,1,1,0,1,1,1,1,1,1,0,1,1,0,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,0,1,0,1},
  185.   {1,1,1,0,0,1,1,1,0,1,1,1,1,1,1,0,1,1,0,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,0,1,0},
  186.   {0,1,0,1,0,1,1,1,1,0,1,1,0,1,1,1,0,0,0,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1},
  187.   {1,0,1,0,1,0,1,1,1,1,0,1,1,1,1,1,1,0,0,0,1,1,0,1,1,1,1,0,0,1,1,1,1,0,1,1,1,1,1,1,1},
  188.   {1,1,0,1,0,1,0,1,1,1,1,0,1,0,1,1,1,1,0,0,0,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1},
  189.   {1,1,1,0,1,0,1,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,0,0,1,1,0,1,0,1,1,1,1,0,1,1,1,1,1},
  190.   {1,1,1,1,0,1,0,1,0,0,1,1,1,0,0,1,1,1,1,1,0,0,0,1,1,0,1,1,1,0,1,0,1,1,1,1,0,1,1,1,1},
  191.   {1,1,1,1,1,0,1,0,1,0,0,1,1,1,0,1,1,1,1,1,1,0,0,0,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1},
  192.   {1,1,1,1,1,1,0,1,0,1,0,0,1,1,1,0,1,1,1,1,1,1,0,0,0,1,0,1,1,0,1,0,1,1,1,1,1,1,0,1,1},
  193.   {1,1,1,1,1,1,1,0,1,1,1,0,0,0,1,0,1,1,1,1,1,1,1,0,0,1,0,0,1,1,0,1,1,1,1,1,1,1,1,0,1},
  194.   {1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,0,1,1,1,1,1,1,1,1,0,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,0}};
  195.  
  196.   return connects[n1][n2];
  197. }
  198.  
  199. /**
  200.  * Whether two nodes are adjacent.
  201.  */
  202. bool adj4(int n1, int n2) {
  203.   static int connects[51][51] = {
  204.   {0,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1},
  205.   {1,0,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1},
  206.   {1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,0,0,1,0,0,1,1,1,1,1,1,1,1,0,1,1,0,0,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1},
  207.   {1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,0,0,1,0,0,1,1,1,1,1,1,1,0,0,0,1,0,0,1,1,1,1,0,1,0,1,1,1,1,1,1,1},
  208.   {1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,0,0,1,1,0,1,0,0,1,1,1,1,1,1,1,0,0,0,1,0,0,1,1,1,1,0,1,0,1,1,1,1,1,1},
  209.   {1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,0,0,1,1,0,1,0,0,1,1,1,1,1,1,1,0,0,0,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1},
  210.   {1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,0,1,1,1,1,1,1,1,0,0,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1},
  211.   {1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,0,1,1,1,1,1,1,1,0,0,0,0,1,1,0,1,1,1,0,1,0,1,1,1},
  212.   {1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,0,0,1,1,1,0,1,0,0,1,1,1,1,1,1,1,0,0,0,0,1,1,0,1,1,1,0,1,0,1,1},
  213.   {1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,0,0,0,1,1,1,0,1,0,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1},
  214.   {1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,0,0,0,1,1,1,0,1,0,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,0},
  215.   {0,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,1,1,1,1,1,1,0,0,1,1,1,0,0,1,1,1,1,1,1,0,1},
  216.   {1,0,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,1,1,1,0,0,1,0,1,0,0,1,1,1,1,1,1,0},
  217.   {0,1,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,1,0,0,1,1,1,1,1,1,0,0,1,0,0,1,1,1,1,1,1,0,0,1,0,0,0,1,0,0,1,1,1,1},
  218.   {1,0,1,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,0,1,1,0,1,1,1,1,1,1,0,1,1,0,0,0,1,0,0,1,1,1},
  219.   {1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,0,1,1},
  220.   {1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,0,0,0,1,0,0,1},
  221.   {1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,0,0,0,1,0,0},
  222.   {0,0,0,1,0,0,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,0,1,0,1},
  223.   {1,0,0,0,1,0,0,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,0,1,1,1,1,1,1,1,1,0,0,1,0},
  224.   {0,0,1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1},
  225.   {1,0,0,1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,0,0,1,0,1,0,0,1,1,1,1,1,1,1,1,1},
  226.   {1,1,0,0,1,0,1,1,1,0,0,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,0,0,0,0,1,0,0,1,1,1,1,1,1,1,1},
  227.   {1,1,1,0,0,1,0,1,1,1,0,0,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,0,0,0,1,0,0,1,1,1,1,1,1,1},
  228.   {1,1,1,1,0,0,1,0,1,1,1,0,0,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,0,1,0,0,1,1,1,1,1,1},
  229.   {1,1,1,1,1,0,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,0,1,1,1,1,1},
  230.   {1,1,1,1,1,1,0,0,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,0,0,1,1,1,0,1,0,0,1,1,1,1},
  231.   {1,1,1,1,1,1,1,0,0,1,0,0,0,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,0,0,1,1,1,0,1,0,0,1,1,1},
  232.   {1,1,1,1,1,1,1,1,0,0,1,0,0,0,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,0,0,1,1,1,0,1,0,0,1,1},
  233.   {1,1,1,1,1,1,1,1,1,0,0,1,0,1,0,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,0,0,0,1,1,1,0,1,0,0,1},
  234.   {1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,1,0,1,1,1,0,0,0,1,1,1,0,1,0,0},
  235.   {0,1,0,0,1,1,1,1,1,1,1,1,0,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,0,0,1,0,0,0,1},
  236.   {1,0,1,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,0,0,1,0,0,0},
  237.   {0,0,1,0,0,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,0,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1},
  238.   {1,0,0,1,0,0,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1},
  239.   {1,1,0,0,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1},
  240.   {1,1,1,0,0,1,0,0,0,1,1,0,1,1,1,1,1,1,0,1,1,0,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,0,1},
  241.   {1,1,1,1,0,0,1,0,0,0,1,0,0,1,1,1,1,1,1,0,0,1,0,0,1,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,0},
  242.   {0,1,1,1,1,1,1,0,0,1,0,1,0,0,1,1,1,1,1,0,1,0,0,0,1,0,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,0,1},
  243.   {1,0,1,1,1,1,1,1,0,0,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,0},
  244.   {0,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,0,1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1},
  245.   {1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,0,1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1},
  246.   {1,1,0,1,0,1,1,1,0,1,1,0,0,0,0,1,1,1,1,1,1,1,0,0,1,0,1,1,1,0,0,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1},
  247.   {1,1,1,0,1,0,1,1,1,0,1,1,0,0,0,0,1,1,1,1,1,1,1,0,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1},
  248.   {1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,0,0,1,1,1,1,1,1,1,0,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1},
  249.   {1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,0,0,0,1,1,1,1,1,1,1,0,0,1,0,1,1,0,0,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1},
  250.   {1,1,1,1,1,1,0,1,0,1,1,1,1,0,0,1,0,0,0,1,1,1,1,1,1,1,0,0,1,0,1,1,0,0,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1},
  251.   {1,1,1,1,1,1,1,0,1,0,1,1,1,1,0,0,1,0,0,0,1,1,1,1,1,1,1,0,0,1,0,0,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1},
  252.   {1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,0,0,1,0,0,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1},
  253.   {1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,0,1},
  254.   {1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,0}};
  255.  
  256.  
  257.   return connects[n1][n2];
  258. }
  259.  
  260. /**
  261.  * Whether two nodes are adjacent.
  262.  */
  263. bool adj5(int n1, int n2) {
  264.   static int connects[53][53] = {
  265.   {0,1,1,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,0,0,1,0,1,1,0,1,0,0,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,0,0,1,1,1,1},
  266.   {1,0,1,1,1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,0,1,0,1,1,0,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1},
  267.   {1,1,0,1,1,1,1,1,0,1,1,0,1,1,1,1,1,1,0,1,0,1,1,0,1,1,1,0,1,1,0,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1},
  268.   {1,1,1,0,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,0,1,0,1,0,0,1,1,1,1,1,0,0,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,0,1},
  269.   {1,1,1,1,0,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,0,0,0,1,1,1,1,1,0,0,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,0},
  270.   {0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0},
  271.   {0,1,1,0,1,1,0,1,1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1},
  272.   {1,0,1,1,0,1,1,0,1,1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,0,0,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,0,1},
  273.   {1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,0,1,1,0,0,1,0,1,1,1,0,0,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,0},
  274.   {0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,0,0,0,0,1,1,0,1,1,1,0,1,1,1,1,1,1},
  275.   {1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,0,0,0,1,1,0,1,1,1,0,1,1,1,1,1},
  276.   {1,1,0,1,1,0,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,0,1,1,1,1,0,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1},
  277.   {1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,0,0,1,0,1,1,1,1,0,1,0,0,0,0,1,1,1,1,0,1,1,1,1,1},
  278.   {1,1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,1},
  279.   {1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,0,1,1,0,1,1,1,0,0,1,1,1,0,1,0,0,0,1,0,1,1,1,0,1,1,1},
  280.   {1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,0,1,1,0,1,1,1,1,0,1,1,1,0,0,1,1,1,1,0,1,1,1,0,1,0,0,1,1,0,1,0,1,0,1,1},
  281.   {1,1,1,1,1,0,1,1,0,0,1,1,1,1,1,1,0,1,1,0,1,1,1,1,1,1,1,0,1,1,0,1,0,1,1,1,1,0,1,1,1,0,1,0,0,1,1,1,1,0,1,0,1},
  282.   {1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,0,1,1,1,1,1,1,1,0,1,0,0,1,0,1,1,1,1,0,1,1,1,0,1,0,0,1,1,1,1,0,1,0},
  283.   {0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,0,1,1,1,0,1,1,1,1,0,1,0,1,0,1,0,1,1,1},
  284.   {1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,0,1,1,1,0,1,1,1,1,1,1,0,0,1,1,0,1,1},
  285.   {1,1,0,1,0,1,1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,0,1,1,0,1},
  286.   {1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,0,1,1,1,0,0,1,1,0},
  287.   {0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,0,0,0,0,1,0,1,1,1,1,1,1,1,1,0,0,0,0},
  288.   {0,1,0,0,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,0,0,1,0,1,1,1,1,0,1},
  289.   {1,0,1,0,0,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,0,0,1,1,1,1,1,1,0},
  290.   {0,1,1,1,0,0,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,0,1,1,1,0,1,1},
  291.   {1,0,1,1,1,0,0,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,0,1,1,1,0,1},
  292.   {1,1,0,1,1,1,0,0,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,0,0,1,1,1,0},
  293.   {0,1,1,1,1,1,1,0,0,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,0,0,1,0,1},
  294.   {1,0,1,1,1,1,0,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,0,0,1,0},
  295.   {0,0,0,0,1,1,1,1,1,1,1,1,0,1,0,0,0,0,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0},
  296.   {0,1,1,0,0,1,1,1,0,1,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1},
  297.   {1,0,1,1,0,0,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,0,1,1,1,1,0,1,1,1,1,0,1,0,1,1},
  298.   {1,1,0,1,1,0,0,1,1,1,1,1,1,0,1,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1},
  299.   {1,1,1,0,1,0,1,0,1,0,1,1,1,1,0,1,1,1,0,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0},
  300.   {0,1,0,1,1,1,1,0,0,1,0,1,1,1,0,1,1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,0,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1},
  301.   {1,0,1,0,1,1,1,1,0,0,1,0,1,1,1,0,1,1,1,1,0,1,0,1,1,0,1,1,1,1,1,1,1,0,1,1,0,1,1,1,1,1,1,0,0,1,1,0,1,1,1,1,1},
  302.   {1,1,0,1,0,1,0,1,1,0,0,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1},
  303.   {1,1,1,0,1,1,1,0,1,0,0,0,1,0,1,1,1,0,0,1,1,1,0,1,1,0,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1},
  304.   {1,1,1,1,0,1,1,1,0,0,0,0,0,1,0,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,0,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,1},
  305.   {1,1,1,1,1,0,1,1,1,1,0,0,0,0,1,0,1,1,1,1,0,1,0,0,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1},
  306.   {1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,0,1,1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,0,0,1,1,0,1,1},
  307.   {1,1,1,1,1,0,1,1,1,0,1,1,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1},
  308.   {1,1,1,1,1,1,0,1,1,1,0,1,1,0,0,0,0,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0},
  309.   {0,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,0,0,1,1,1,0,1,0,0,1,1,0,1,1,1,1,1,1,1,1,0,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1},
  310.   {1,0,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,0,0,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,1,1,0,1,1,0,1,1,0,1},
  311.   {1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,1,1,0,1,1,0,1,1,0},
  312.   {0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,0,0,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0},
  313.   {0,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,0,0,1,1,1,1,1,0,0,0,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,0,1,1,1,1},
  314.   {1,0,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,0,0,1,1,1,1,1,0,0,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,0,1,1,1},
  315.   {1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,1,0,1,1,0,1,0,1,1,1,1,1,1,0,1,1,0,1,1,1,1,1,0,1,1},
  316.   {1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,0,1,1,0,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,0,1,1,1,1,1,0,1},
  317.   {1,1,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,0,0,1,0,1,1,0,1,0,0,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,0,0,1,1,1,1,0}};
  318.  
  319.  
  320.   return connects[n1][n2];
  321. }
  322.  
  323. int main() {
  324.   cout << max_clique(9, adj1) << endl;
  325.   cout << max_clique(23, adj2) << endl;
  326.   cout << max_clique(41, adj3) << endl;
  327.   cout << max_clique(51, adj4) << endl;
  328.   cout << max_clique(53, adj5) << endl;
  329.   return 0;
  330. }
Success #stdin #stdout 0.98s 3444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
8
9
11
13
https://ideone.com/Os2Gwk
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!