bzoj#P3023. [Balkan2012]Fan Groups

[Balkan2012]Fan Groups

题目描述

给定一个有向图,每个节点关联于一群人。这 n n 群人按照某个特定的顺序进行以下操作:

  • 到达并占领他们关联的节点;
  • 从他们占领的某个节点 u u 出发,走到与其相邻的每个点 v v 。如果点 v v 已经被人占领,他们会边 (u,v) (u,v) 上发生冲突,并不再在这个方向上前进;否则,他们会占领点 v v ,并重复这一步,直到没有能到达的点为止。
  • 如果他们关联的节点在此前被别的人群占领,他们不会与那群人发生冲突。在这种情况下,他们什么都不做。

给定该图,以及发生冲突的边集。求一种人群的行动顺序,使得发生冲突的边集与输入相符。

以样例为例。关联于点 8 8 的人群首先行动,占领点 8 8 ;接下来关联于点 5 5 的人群行动,占领点 4,5,6 4,5,6 (与 4 4 相连的点 集);关联于点 6 6 的人群出动,因为点 6 6 已经被占领,他们什么都不做;人群 2 2 占领点 2,3 2,3 ;人群 3 3 什么都不做;人 群 1 1 占领点 1 1 ,并在边 <1,4> <1,4> <1,8> <1,8> 上引发冲突;人群 7 7 占领点 7 7 并在边 <7,1> <7,1> <7,4> <7,4> 上引发冲突;人群 4 4 什么都不做。

注意合法的顺序可能不止一种;样例中, (2,3,8,4,1,7,5,6) (2, 3, 8, 4, 1, 7, 5, 6) 也是一种合法的方案。注意 (8,5,6,3,2,1,7,4) (8, 5, 6, 3, 2, 1, 7, 4) 不是合法的方案,因为按照这个方案,<2,3> <2,3> 上也会发生冲突,与输入不符。

输入格式

输入的第一行包含两个整数 n,m n,m ,含义是点数和边数。

接下来 m m 行,每行三个整数 A,B,C A,B,C ,表示有向边 AB A\to B ,如果 C=1 C=1 ,则这条边上发生了冲突。

输出格式

输出一个排列,表示人群的行动顺序。

如果没有任何顺序满足题意,输出-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

数据规模与约定

对于 100%100\% 的数据,n2×104 n\leq 2\times 10^4 m2×105 m \leq 2\times 10^5

题目来源

Dragonite提供SPJ