问题1271--【搜索基础】部落卫队

1271: 【搜索基础】部落卫队

时间限制: 2 Sec  内存限制: 128 MB
提交: 34  解决: 4
[提交] [状态] [讨论版] [命题人:]

题目描述

部落卫队  inde.pas 
【问题描述】 
为了组织一支部队,希望选出最多的人入伍,并保证队伍中任何2个人不是仇敌。给定每人的仇敌关系,求最佳方案
【输入格式】 
第一行2个正整数nm,表示n个人,m个仇敌关系,接下来m行,每行2个正整数uv,表示uv是仇敌(人编号1..n
【输出格式】 
第一行是最多的人数,第二行是队伍的组成Xi0表示第i个人不入伍,1表示入伍
【问题规模】  
1<=n<=100,   0<=m<=5000 

 


输入




样例输入

7 10
1 2
1 4
2 4
2 3
2 5
2 6
3 5
3 6
4 5
5 6

样例输出

3
1 0 1 0 0 0 1

来源/分类


[提交] [状态]