さいだいだんもんだい

Maximum Clique
杭電OJ Maximum Clique Time Limit:20000/1000 MS(Java/others)Memory Limit:65536/32768 K(Java/others)Total Submission(s):6637 Accepted Submission(s):3371
Problem Description Given a graph G(V, E), a clique is a sub-graph g(v, e), so that for all vertex pairs v1, v2 in v, there exists an edge (v1, v2) in e. Maximum clique is the clique that has maximum number of vertex.
Input Input contains multiple tests. For each test:
The first line has one integer n, the number of vertex. (1 < n <= 50)
The following n lines has n 0 or 1 each, indicating whether an edge exists between i (line number) and j (column number).
A test with n = 0 signals the end of input. This test should not be processed.
Output One number for each test, the number of vertex in maximum clique.
Sample Input 5 0 1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 0
Sample Output 4
java

import java.util.Scanner;
public class Main {
	static long count = 0;	//           
	static int [][]a;	//      
	static int []x;		//x[i] == 1，        i  。
	static int v;		//    
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		while((v = sc.nextInt())!=0){
			a = new int[v+1][v+1];
			x = new int[v+1];

			for(int i=1;i<=v;i++)
				for(int j=1;j<=v;j++)
					a[i][j] = sc.nextInt();
			
			//                O（2^v）,               。
			backtrack(1,0);
			System.out.println(count);
			count = 0;
		}
	}
	static void backtrack(int t,int n){		//t     ，n           
		if(t>v) {
			count = n;
			//print();
			return;
		}
		//      （ t  ）    t-1       
		//            ，    
		if(yueshu(t)){
			//     ，      ，   
			x[t] = 1;	//   t  
			backtrack(t+1,n+1);	//  +1.       +1，
		}
		// v-t        ，            。
		//n + v-t           。                                   
		//     
		if(n + v-t>count) {
			//   
			x[t] = 0;
			backtrack(t+1,n);
		}
	}
	static boolean yueshu(int t){
		for(int j=1;j<t;j++)
	        if(x[j] == 1&&a[t][j] == 0) {
	            return false;
	        }
		
		return true;
	}
}

CPP
遡及法の最大の問題は時間が長く、タイムアウトしやすいことです.

#include 
using namespace std;
long count_v = 0;	//           
int a[55][55];	//      
int x[55];		//x[i] == 1，        i  。
int v;		//    
static bool yueshu(int t) {
	for (int j = 1; j < t; j++)
		if (x[j] == 1 && a[t][j] == 0) {
			return false;
		}

	return true;
}
static void backtrack(int t, int n) {		//t     ，n           
	if (t > v) {
		count_v = n;
		//print();
		return;
	}
	//      （ t  ）    t-1       
	//            ，    
	if (yueshu(t)) {
		//     ，      ，   
		x[t] = 1;	//   t  
		backtrack(t + 1, n + 1);	//  +1.       +1，
	}
	// v-t        ，            。
	//n + v-t           。                                   
	//     
	if (n + v - t > count_v) {
		//   
		x[t] = 0;
		backtrack(t + 1, n);
	}
}

int main()
{
	while ((cin>>v) && v!= 0) {


		for (int i = 1; i <= v; i++)
			for (int j = 1; j <= v; j++)
				cin>>a[i][j];

		//                O（2^v）,               。
		backtrack(1, 0);
		cout << count_v << endl;
		count_v = 0;
	}
	return 0;
}