Submission #111764

---

Source Code Expand

#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
int n,m;
int com[144];
int ans=1;
vector<int>siriai[12];
int siriai_num[12];
int bina[12];
int men[12];
int men_num;
int target;
int check(int t)//リストでt番目の人の友達状態
{
	for(int i=0;i<men_num;i++)
	{
		if(i==t)continue;
		target=men[i];
		for(int j=0;j<siriai_num[men[t]];j++)
		{
			if(siriai[men[t]][j]==target)break;
			if(j==siriai_num[men[t]]-1)return 0;
		}
	}
	return 1;
}

void saiki(int s)
{
	if(s<n)
	{
		for(int i=1;i>=0;i--)
		{
			bina[s]=i;
			saiki(s+1);
		}
	}
	else
	{
		men_num=0;
		for(int i=0;i<n;i++)
		{
			if(bina[i]==1)
			{
				men[men_num]=i;
				men_num++;
			}
		}
		int flag=1;
		for(int i=0;i<men_num;i++)
		{
			flag*=check(i);
		}
		if(flag==1)
		{
			if(ans<men_num)
			{	
				ans=men_num;
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	if(m==0)
	{
		cout<<1<<endl;
		return 0;
	}
	int x,y;
	for(int i=0;i<n;i++)
	siriai_num[i]=0;
	for(int i=0;i<m;i++)
	{
		cin>>x>>y;
		x--;
		y--;
		siriai[x].push_back(y);
		siriai[y].push_back(x);
		siriai_num[x]++;
		siriai_num[y]++;
	}
	saiki(0);
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result