3561300_tle.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main {
	private Scanner in;
	private int n;
	private boolean[][] map;
	private final boolean BLACK = false;
	private final boolean WHITE = true;
	private boolean[] color;
	private boolean[] result;

	public static void main(String[] args) {
		new Main().run();
	}

	private void run() {
		in = new Scanner(System.in);
		int cas;
		int m;

		cas = in.nextInt();
		while (cas-- > 0) {
			n = in.nextInt();
			/*
			if (n > 40) {
				while (true) {
					System.out.println("I love Shengqi");
				}
			}
			*/
			map = new boolean[n][n];
			color = new boolean[n];
			result = new boolean[n];
			m = in.nextInt();
			for (int i = 0; i < m; i++) {
				int u = in.nextInt() - 1;
				int v = in.nextInt() - 1;
				map[u][v] = map[v][u] = true;
			}
			long max = (1L << n);
			int ans = 0;
	label:	for (long i = 0; i < max; i++) {
				long tmp = 1;
				int cnt = 0;
				for (int j = 0; j < n; j++, tmp <<= 1) {
					if ((i & tmp) != 0) {
						color[j] = BLACK;
						cnt++;
					} else {
						color[j] = WHITE;
					}
				}
				if (cnt <= ans) {
					continue;
				}
				for (int j = 0; j < n; j++) {
					if (color[j] == BLACK) {
						for (int k = 0; k < n; k++) {
							if (map[j][k] && color[k] == BLACK) {
								continue label;
							}
						}
					}
				}
				ans = cnt;
				System.arraycopy(color, 0, result, 0, n);
			}
			System.out.println(ans);
			for (int i = 0; i < n; i++) {
				if (result[i] == BLACK) {
					ans--;
					System.out.print((i + 1));
					if (ans != 0) {
						System.out.print(" ");
					}
				}
			}
			System.out.println();
		}
	}
}