返回信息流求问Question4， 粗略翻译如下：
假设一个社交网络内有一群人，他们每个人都有一个只有两种可能的“偏好”（比如：喜欢Mac或PC）。每个人都与他的“朋友们”相连，他们的朋友们也都是这个网络中的人。 现在你可以在这个网络中任意选择一个人，使这个人看到他的朋友们的偏好：如果他的大部分朋友都有同一种偏好，则这个被选中的人也会将他的偏好设为这个偏好； 如果他的朋友中喜欢Mac和喜欢PC的各占一半，则你可以为他选择一种偏好。假设这个网络是连通的，我们能否总是找到一序列的人，使得他们最终都有同样的偏好？
我没有学过数据结构也没有学过图论...这道题应该属于元胞自动机吗？还是求连通分量？有没有大神可以帮助我解一下题？愿意附上酬劳100元 T-T
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #91696同步于 2016/11/22
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
有偿求解：这个问题属于求连通分量吗
se7en
2016/11/22镜像同步5 回复
订阅后，新回复会通过你的通知中心匿名送达。
5 条回复
我也是觉得初始状态描述得不太清楚
假设我可以选一个人，让他知道自己朋友的偏好。
那么他朋友从哪里知道自己的偏好的？总要有一个初始位置吧。
而且我觉得，假设他的朋友中有一些没有偏好，那么如何算？
那么按照上面的逻辑，我这么假设这个过程。
假设初始状态所有人都是没有偏好的，那么随便选一个人，他的朋友的偏好中mac和PC的偏好都等于0，所以我自己给他选一个PC。
然后就发现，这个网格里面要么是选择PC的，那么他的朋友肯定是选择PC。如果他没有偏好，我都给他选PC。
所以最终结果应该是，大家都是PC.......
楼下的反例已经把你的猜想证伪了...
我觉得直接贪心就可以了。假设现在想全部变成黑色，那本来就是黑的点始终不要动，然后所有白色的点，根据邻居的情况，能翻转的就翻转，整个图黑的越来越多，直到翻不动了或者全变黑了就停。如果没法全翻成黑的，就再尝试全翻成白的，要是也不能全翻成白的，那就无解了。这么贪心的话能保证，如果存在一个解，那么贪心策略一定能把它找到。实现上就跟拓扑排序差不多，每次翻转就把它的邻居顶点的状态（黑白个数）更新一下。
【 在 wangzitian0 的大作中提到: 】
: 大胆猜想，图里喜欢哪种pc的比较多，图最终会变成全喜欢那一种……