乡村教师

Grade 100 Open Time Wednesday, 17 June 2020, 10:10 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 10:10 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 10:10 PM
Input file teacher.in Output file teacher.out

【题目描述】乡村教师(teacher)codevs 1332

有一位乡村教师,为N个村庄授课,因为很多道路被破坏,有的学生不能顺利地到达他所在的村庄。因此他决定换一个能够聚集最多人数的村庄作为新的教学点。已知有M条道路,道路有单向通行的,也有双向通行的,分别用1和2来标记。

现在你的任务是:找出最大的绝对连通区域,并将这个绝对连通区域的村庄按编号依次输出。若存在两个最大的,输出字典序最小的,比如当存在1,2,3和2,3,4这两个最大连通区域时,输出的是1,2,3。

【输入格式】

第1行为两个正整数N和M。

随后M行中,每行三个正整数x,y,t,t=1表示存在从x村庄到y村庄的单向道路,t=2表示x村庄和y村庄存在双向通行道路,保证每条道路只出现一次。

【输出格式】

第1行为一个整数,表示最大的绝对连通区域包含的村庄个数。

第2行为若干个整数,依次输出最大的绝对连通区域所包含的村庄编号。

【输入样例】

5 5

1 2 1

2 4 1

4 1 1

4 3 1

3 5 2

【输出样例】

3

1 2 4