Submission #112253

---

Source Code Expand

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	private static Human[] humanArray;
	private List<Integer> visitedList;
	private int friendIndex;
	private int max = 1;

	/** コンストラクタ */
	public Main(){
		this.visitedList = new ArrayList<Integer>();
	}
	
	private boolean checkFriend(int num){
		boolean tf = true;
		
		for(int i=0;i<this.visitedList.size();i++){
			if(humanArray[this.visitedList.get(i)].friendList.indexOf(num) == -1){
				tf = false;
				break;
			}
		}
		
		return tf;
	}
	
	private void countFriend(){
		int ans = 1;
		for(int i=0;i<humanArray.length;i++){
			if(this.max >= humanArray.length-i){
				break;
			}
			this.friendIndex = -1;
			ans = countFriend(i);

			if(this.max < ans){
				this.max = ans;
			}
		}
	}
	
	private int countFriend(int num){
		int save = 0;
		int ans = 0;
		int checkNum;
		if(this.visitedList.size() == 1){
			this.friendIndex++;
		}
		this.visitedList.add(num);
		List<Integer> list = humanArray[num].friendList;
		
		for(int i=0;i<list.size();i++){
			checkNum = humanArray.length-this.visitedList.get(0)-this.friendIndex+1;
			if(this.max>=checkNum || ans+1>=checkNum){
				break;
			}
			if(list.get(i) <= this.visitedList.get(0)){
				continue;
			}
			if(this.visitedList.size()>=2 && list.get(i)<this.visitedList.get(1)){
				continue;
			}
			if(this.visitedList.indexOf(list.get(i)) == -1){
				if(checkFriend(list.get(i))){
					save = countFriend(list.get(i));
					if(ans < save){
						ans = save;
					}
				}
			}
		}
		this.visitedList.remove(this.visitedList.size()-1);
		
		return ans + 1;
	}
	
	/** mainメソッド */
	public static void main(String[] args) {
		Main main = new Main();
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();
		humanArray = new Human[n];
		
		for(int i=0;i<n;i++){
			humanArray[i] = main.new Human();
		}
		
		for(int i=0;i<m;i++){
			int x = scan.nextInt();
			int y = scan.nextInt();
			humanArray[x-1].friendList.add(y-1);
			humanArray[y-1].friendList.add(x-1);
		}
		
		main.countFriend();
		
		System.out.println(main.max);
	}
	
	private class Human{
		private List<Integer> friendList;
		
		/** コンストラクタ */
		private Human(){
			this.friendList = new ArrayList<Integer>();
		}
	}
}

Submission Info

Judge Result