Submission #5014304

---

Source Code Expand

import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt();
			int m = scanner.nextInt();
			scanner.nextLine();
			boolean relation[][] = new boolean[n][n];
			IntStream.range(0, n).forEach(i -> {
				IntStream.range(0, n).forEach(j -> relation[i][j] = false);
			});
			IntStream.range(0, n).forEach(i -> relation[i][i] = true);
			IntStream.range(0, m).forEach(i -> {
				int x = scanner.nextInt();
				int y = scanner.nextInt();
				scanner.nextLine();
				relation[x - 1][y - 1] = relation[y - 1][x - 1] = true;
			});
			List<Integer> list = IntStream.range(1, (int) Math.pow(2, n)).boxed()
					.sorted((x, y) -> oneCount(y) - oneCount(x)).collect(Collectors.toList());
			for (Integer integer : list) {
				Set<Integer> set = new HashSet<>();
				for (int j = 0; j < n; j++) {
					if (1 == (1 & (integer >> j))) {
						set.add(j);
					}
				}
				if (check(set, relation)) {
					System.out.println(set.size());
					break;
				}
			}
		}
	}

	/**
	 * @param x
	 * @return xの2進数表現の1の数
	 */
	private static int oneCount(int x) {
		int count = 0;
		for (int i = 0; i < 32; i++) {
			if (1 == (1 & (x >> i))) {
				count++;
			}
		}
		return count;
	}

	private static boolean check(Set<Integer> set, boolean[][] relation) {
		for (Integer i : set) {
			for (Integer j : set) {
				if (!relation[i][j]) {
					return false;
				}
			}
		}
		return true;
	}
}

Submission Info

Judge Result