CSC 310 Code Vertex Cover, Spring 2013

import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class VC { public static void main(String[] args) throws FileNotFoundException { File f = new File("graph.in"); Scanner scan = new Scanner(f); int testcases = scan.nextInt(); for (int i = 0; i < testcases; i++) { int nodes = scan.nextInt(); int edges = scan.nextInt(); int[][] al = new int[nodes][nodes]; int[] deg = new int[nodes]; for (int j = 0; j < edges; j++) { int u = scan.nextInt(); int v = scan.nextInt(); al[u][deg[u]++] = v; al[v][deg[v]++] = u; } int k =scan.nextInt(); System.out.println(VC(al,deg,k)); } } public static int getMax(int[] A) { int index = 0; for(int i = 1;i<A.length;i++) if(A[i] > A[index]) index = i; return index; } public static boolean DeleteEdge(int[][] al, int[] d, int u, int v) { for(int i = 0;i<d[u];i++) { if(al[u][i] == v) { int temp = al[u][(d[u]-1)]; al[u][(d[u]-1)] = v; al[u][i] = temp; d[u]--; return true; } } return false; } public static void DeleteVertex(int[][] al, int[] d, int v) { for(int i = 0;i<d[v];i++) DeleteEdge(al,d,al[v][i],v); d[v] = 0; } public static boolean edgeless(int deg[]) { for(int i = 0;i<deg.length;i++) if(deg[i] > 0) return false; return true; } public static void insert(int[][] al, int[] d, int v) { for(int i = 0;i<d[v];i++) DeleteEdge(al,d,al[v][i],v); d[v] = -1; } public static boolean VC(int[][] al, int[] d, int k) { int[] temp = new int[d.length]; int v = getMax(d); if(d[v] < 2) while(!edgeless(d)){ v = getMax(d); insert(al,d,v); k--; } if(k < 0) return false; if(edgeless(d)) return true; if(k == 0) return false; for(int i = 0;i<d.length;i++) temp[i] = d[i]; insert(al,temp,v); if(VC(al,temp,k-1)){ for(int i = 0;i<d.length;i++) d[i] = temp[i]; return true; } if(d[v] > k) return false; for(int i = 0; i < d[v]; i++){ insert(al,d,al[v][i]); k--; } return VC(al,d,k); } }