SSOJ2366部落卫队
2698+
作者：crxis 发布：2017-07-29 分类：深度优先搜索
题目大意：从n个居民里选出最多的互不发生冲突的人加入保卫部落的队伍，已知居民的冲突关系，如果选人？
题目描述
原始部落byteland中的居民们为了争夺有限的资源，经常发生冲突。几乎每个居民都有他的仇敌。部落酋长为了组织一支保卫部落的队伍，希望从部落的居民中选出最多的居民入伍，并保证队伍中任何2个人都不是仇敌。
编程任务：
给定byteland部落中居民间的仇敌关系，编程计算组成部落卫队的最佳方案。
输入
第一行有2个正整数n和m，表示byteland部落中有n个居民，居民间有m个仇敌关系。居民编号1,2,3…,n。接下来的m行中，每行有2个正整数u和v，表示居民u与居民v是仇敌。
输出
第一行是部落卫队的总人数；第二行是卫队组成xi，1<=i<=n,xi=0表示居民i不在卫队中，xi=1表示居民i在卫队中。
样例输入
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
解题思路
n个格子，要么填0，要么填1。随时都可以填0，填1的话需要判断是否与前面冲突。填完后，记录最多1的个数，以及填法。
可行性剪枝：如果想选第k个人，就必须扫描前面k-1个人，其中选了的人不能与第k个人发生冲突。（必须，不然最后才判断是否可行，2的100次方中方案会超时）
最优性剪枝：如果选了s个人，还剩下n-k+1个人还没确定选不选，但s+n-k+1不大于（<=）ans，那么后面就不会更好、不用看了。（本题不写也可以过，但很多题目最优性剪枝能大大提高速度）
程序实现
