Submission #111877

---

Source Code Expand

// http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3381

import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

	static int n, m, max;
	static int[] x, y;
	static boolean[] use;
	static boolean[][] friends;
	public static void main(String[] args) {
		doIt();
	}
	static void doIt() {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		x = new int[12];
		y = new int[12];
		use = new boolean[12];
		friends = new boolean[12][12];
		n = sc.nextInt();
		m = sc.nextInt();
		max = -1;
		for(int i = 0; i < m; i++){
			x[i] = sc.nextInt();
			y[i] = sc.nextInt();
			friends[x[i]-1][y[i]-1] = true;
			friends[y[i]-1][x[i]-1] = true;
		}
		System.out.println(rec(0));

	}

	static int rec(int pos){
		int ret = 0;
		if(pos == n){
			for(int i = 0; i < n; i++){
				if(use[i]){
					ret++;
					for(int j = i+1; j < n; j++){
						if(use[j]){
							if(!friends[i][j]) return -1;
						}
					}
				}
			}
			return ret;
		}
		else{
			use[pos] = false;
			ret = Math.max(rec(pos+1), ret);
			use[pos] = true;
			ret = Math.max(rec(pos+1), ret);
			use[pos] = false;
		}
		return ret;
	}

}

Submission Info

Judge Result