0

在新灿学习的双叶幼儿园，有s_0, s_1...s_(N-1)包括新灿在内的N名学生。每个学生都直接或间接地相互认识。两个学生如果是朋友，就直接认识对方。间接认识意味着有第三个学生同时认识他们。相互认识是一种对称关系，即如果学生 s_a 认识学生 s_b，那么学生 s_b 也认识学生 s_a。

爱酱是班上的新学生。她想和他们所有人成为朋友。但是要和那里的N个学生中的每一个交朋友会很麻烦。所以她决定和他们中的一些人交朋友，这样班里的每个学生要么是她的朋友，要么是她朋友的朋友。

帮助她选择那些学生，以便与他们成为朋友将完成她的目标。学生人数越少越好。

输入

输入的第一行将包含两个空格分隔的整数，NM，Futaba 幼儿园的学生人数，不包括 Ai-chan，以及彼此成为朋友的学生对的数量，即他们直接相互认识。然后遵循 M 行。在每一行中，有两个空格分隔的整数 s_u s_v，这样学生 s_u 和 s_v 是彼此的朋友。

输出

在第一行打印这些学生的总数 P。然后在下一行打印 P 空格分隔的学生索引，这样与他们成为朋友将有助于 Ai-chan 实现她的目标。

约束：

1 <= N <= 10^5

1 <= M <= min(10^5, N*(N-1)/2)

0 <= s_u, s_v <= N-1

s_u != s_v

每对学生 (s_u, s_v) 直接或间接地相互认识。

分数：((NP)/N)*200

**Sample Input**
6 7
0 1
0 2
1 2
1 3
2 4
3 4
3 5

**Sample Output**
4
0 2 3 5

我认为只与 1 和 3 成为朋友就可以了。我错过了什么吗？我不是在寻找解决方案，只是对示例输入和输出的解释。

4

1 回答 1

-1

解决方案是一个简单的贪心算法。假设 C 是学生的集合。

S = {}
R = {}
while (C != {}) {
   - sort the students based on their number of friends
   - pick the student s with the highest number of friends
   - add R = R + {s}
   - add s and friends of s to the set S and remove them from C
}
print(R)
于 2013-06-09T11:03:53.337 回答