bzoj#P3023. [Balkan2012]Fan Groups
[Balkan2012]Fan Groups
题目描述
给定一个有向图,每个节点关联于一群人。这 群人按照某个特定的顺序进行以下操作:
- 到达并占领他们关联的节点;
- 从他们占领的某个节点 出发,走到与其相邻的每个点 。如果点 已经被人占领,他们会边 上发生冲突,并不再在这个方向上前进;否则,他们会占领点 ,并重复这一步,直到没有能到达的点为止。
- 如果他们关联的节点在此前被别的人群占领,他们不会与那群人发生冲突。在这种情况下,他们什么都不做。
给定该图,以及发生冲突的边集。求一种人群的行动顺序,使得发生冲突的边集与输入相符。
以样例为例。关联于点 的人群首先行动,占领点 ;接下来关联于点 的人群行动,占领点 (与 相连的点 集);关联于点 的人群出动,因为点 已经被占领,他们什么都不做;人群 占领点 ;人群 什么都不做;人 群 占领点 ,并在边 和 上引发冲突;人群 占领点 并在边 和 上引发冲突;人群 什么都不做。
注意合法的顺序可能不止一种;样例中, 也是一种合法的方案。注意 不是合法的方案,因为按照这个方案, 上也会发生冲突,与输入不符。
输入格式
输入的第一行包含两个整数 ,含义是点数和边数。
接下来 行,每行三个整数 ,表示有向边 ,如果 ,则这条边上发生了冲突。
输出格式
输出一个排列,表示人群的行动顺序。
如果没有任何顺序满足题意,输出-1
。
样例输入
8 9
1 4 1
1 8 1
2 3 0
5 6 0
6 5 0
7 4 1
6 4 0
7 1 1
4 5 0
样例输出
8 5 6 2 3 1 7 4
数据规模与约定
对于 的数据,,。
题目来源
Dragonite提供SPJ