Submission #145126

---

Source Code Expand

import java.util.Scanner;

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

	void run()
	{
		Scanner cin = new Scanner(System.in);
		int N = cin.nextInt();
		int M = cin.nextInt();

		//友人情報を2次元配列に入れる
		boolean[][] friend = new boolean[N][N];
		for(int i=0;i<M;i++){
			int a = cin.nextInt() - 1;
			int b = cin.nextInt() - 1;
			friend[a][b] = friend[b][a] = true;
		}

		int ret = 0;

		//forループとbitを用いた全列挙
		for(int i=0;i<(1<<N);i++){
			//この派閥の人数を数える
			int count = 0;

			boolean flag = true;
			//任意のペアに対し、友達になっているかを確認する。
			for(int a=0;a<N;a++){
				if((i>>a)%2==0) continue;
				count++;
				for(int b=a+1;b<N;b++){
					if((i>>b)%2==0) continue;
					if(!friend[a][b]){
						flag = false;
					}
				}

			}
			if(flag) ret = Math.max(ret, count);
		}
		System.out.println(ret);
	}
}

Submission Info

Judge Result