BOTTOM - The Bottom of a Graph

题意翻译

## 题目描述: V个点,E条单向边,定义link点:一个点u所能到达的点,反过来都能到达u,那么点u就是link点。升序输出所有的link点。 ## 输入输出格式 ### 输入格式: 多组数据直到V=0时结束 每组数据第一行是$V,E\: (1<=V<=5000)$ 第二行是$v_1,w_1,v_2,w_2...v_E,w_E$ 其中$v_i,w_i$表示从$v_i$到$w_i$的一条有向边 ### 输出格式: 对于每组数据,一行内升序输出符合题面要求的点的序号(每个后面加个空格)。如果这样的点不存在,则输出一个空行。 ## 输入输出样例 ### 输入样例: ``` 3 3 1 3 2 3 3 1 2 1 1 2 0 ``` ### 输出样例: ``` 1 3 2 ```

题目描述

MathJax.Hub.Config({ tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], skipTags: ["script","noscript","style","textarea","code"] } }); We will use the following (standard) definitions from graph theory. Let $V$ be a nonempty and finite set, its elements being called vertices (or nodes). Let $E$ be a subset of the Cartesian product $V \\times V$, its elements being called edges. Then $G = (V, E)$ is called a directed graph. Let $n$ be a positive integer, and let $p = (e\_1, \\ldots, e\_n)$ be a sequence of length $n$ of edges $e\_i \\in E$ such that $e\_i = (v\_i, v\_{i+1})$ for a sequence of vertices ($v\_1, \\ldots, v\_{n+1}$). Then $p$ is called a path from vertex $v\_1$ to vertex $v\_{n+1}$ in $G$ and we say that $v\_{n+1}$ is reachable from $v\_1$, writing $(v\_1 \\to v\_{n+1})$. Here are some new definitions. A node $v$ in a graph $G = (V, E)$ is called a sink, if for every node $w$ in $G$ that is reachable from $v$, $v$ is also reachable from $w$. The bottom of a graph is the subset of all nodes that are sinks, i.e., $\\mathrm{bottom}(G) = \\{v \\in V \\mid \\forall w \\in V : (v \\to w) \\Rightarrow (w \\to v) \\}$. You have to calculate the bottom of certain graphs.

输入输出格式

输入格式


输出格式


输入输出样例

暂无测试点