← 返回题目

题库练习部落卫队

← 上一题下一题 →

A229 | $部落卫队$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

原始部落 $byteland$ 中的居民们为了争夺有限的资源，经常发生冲突。几乎每个居民都有他的仇敌。部 落酋长为了组织一支保卫部落的队伍，希望从部落的居民中选出最多的居民入伍，并保证队伍中任何 $2$ 个 人都不是仇敌。 给定 $byteland$ 部落中居民间的仇敌关系，编程计算组成部落卫队的最佳方案。

输入格式

第一行 $2$ 个正整数 $n$ 和 $m$，表示 $n$ 个人，$m$ 个仇敌关系，接下来 $m$ 行，每行 $2$ 个正整数 $u$ 和 $v$，表示 $u$ 和 $v$ 是仇敌（人编号 $1..n$）。

输出格式

第一行是最多的人数，第二行是队伍的组成 $X_i$，$0$ 表示第 $i$ 个人不入伍，$1$ 表示入伍。

输入输出样例

输入 #1

输出 #1

3
1 0 1 0 0 0 1

C++ 编辑器

输入

输出