Submission #448665

---

Source Code Expand

import java.io.*;
import java.util.Scanner;
import java.util.Arrays;
import static java.lang.Math.*;

public class Main {
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		int N, M;
		boolean[][] relation;
		N = sc.nextInt();
		M = sc.nextInt();
		
		relation = new boolean[N+1][];
		for(int i = 0; i <= N; i++){
			relation[i] = new boolean[N+1];
			for(int j = 0; j <= N; j++){
				relation[i][j] = false;
			}
		}
		
		for(int i = 0; i < M; i++){
			int X, Y;
			X = sc.nextInt();
			Y = sc.nextInt();
			X--;
			Y--;
			relation[X][Y] = relation[Y][X] = true;
		}
		
		int ans = 0;
		
		for(int ret = 0; ret < (1 << N); ret++){
			
			boolean flag = true;
			
			for(int i = 0; i < N; i++){
				if(!flag)
					break;
				if(((ret >> i) & 1) == 1){
					for(int j = i+1; j < N; j++){
						if(((ret >> j) & 1) == 1){
							if(!relation[i][j]){
								flag = false;
								break;
							}
						}
					}
				}
			}
			
			if(flag){
				int tmp = 0;
				for(int i = 0; i < N; i++){
					if(((ret >> i) & 1) == 1){
						tmp++;
					}
				}
				ans = max(ans, tmp);
			}
			
		}
		
		System.out.println(ans);
		
		sc.close();
		
	}
	
}

Submission Info

Judge Result