1948. eelpi和迷宫出口

时间限制 2000 ms   内存限制 512 MB

eelpi是一个异世界的剑士!

现在,eelpi被困在了一个迷宫里,这个迷宫可以看作一个有 $n$ 个结点(用 $[1,n]$ 的序号表示),$m$ 条边的弱连通(所有的有向边替换为无向边后的图为连通图)的有向无环图,并且图中有一个出口在结点 $S$,eelpi需要找到这个出口 $S$!

eelpi还会法术,他通过法术知道了对于每个结点 $u$,都有一个值 $g_u$,表示通过起点为 $u$ 的边 $u\to v$ 后仍然能到达 $S$ 的 $v$ 的数量(即 $v$ 就是 $S$ 或者 $v$ 能到 $S$,很明显 $g_S=0$)。

现在eelpi想知道有哪些结点可能是出口,也就是 $S$ 点,但是他需要集中精力面对迷宫里的怪兽,所以请你帮助他解决这个问题吧!

输入数据

由于本题数据量很大,所以请勿使用过慢的输入输出方式。特别的,C++选手请勿使用没有关闭流同步的cincout、Java选手请勿使用Scanner

第一行两个整数$n,m (2\le n\le 10^5,1\le m\le 10^6)$,分别表示点和边的数量。
接下来一行 $n$ 个整数,其中第 $i$ 个整数表示 $g_i\ (0\le g_i\le n)$。
接下来一共 $m$ 行,每行两个整数 $u,v(1\le u\le n,1\le v\le n,u\not=v)$,表示有一条从 $u$ 到 $v$ 的有向边。
输入数据保证给出的图是弱连通的有向无环图,并且没有重边,也就是不会有某两行的$u,v$分别相等。
输入保证至少能找到一个点是 $S$ 点。

输出数据

第一行为一个整数 $cnt$,表示有多少个点可能是 $S$。
第二行为 $cnt$ 个整数,按编号从小到大的顺序输出可能是 $S$ 的点。

样例输入

复制
5 5
1 1 0 0 0
1 2
2 3
1 3
1 4
2 5 · \n
 · · · · \n
 · \n
 · \n
 · \n
 · \n
 · \n

样例输出

复制
1
5 \n
 \n

样例说明

当 $S=5$ 时

  1. $g[1]$ 只能由 $\langle1,2\rangle$ 这条边前往 $S$,所以 $g_1=1$;
  2. $3$ 和 $4$ 到不了 $S$,所以 $g_3,g_4=0$;
  3. $2$ 只能通过 $\langle2,5\rangle$ 到达 $S$,所以 $g_2=1$;
  4. $5$ 自身就是 $S$ 点,所以 $g_S=0$。

可以证明,如果令其他点是 $S$,则无法满足给出的 $g$ 的数值。

提交

请先 登录

© 2024 FAQs Contact About