# POJ 2553(The Bottom of a Graph-ç¼©ç‚¹و±‚ه‡؛ه؛¦)

Language:
The Bottom of a Graph
 Time Limit:آ 3000MS آ Memory Limit:آ 65536K Total Submissions:آ 7308 آ Accepted:آ 3003

Description

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أ—V, its elements being called edges.
Thenآ G=(V,E)آ is called a directed graph.آ
Letآ nآ be a positive integer, and letآ p=(e1,…,en)آ be a sequence of lengthآ nآ of edgesآ eiâˆˆEآ such thatآ ei=(vi,vi+1)آ for a sequence of verticesآ (v1,…,vn+1).
Thenآ pآ is called a path from vertexآ v1آ to vertexآ vn+1آ inآ Gآ and we say thatآ vn+1آ is reachable fromآ v1, writingآ (v1â†’vn+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.,bottom(G)={vâˆˆV|âˆ€wâˆˆV:(vâ†’w)â‡’(wâ†’v)}. You have to calculate the bottom of certain graphs.

Input

The input contains several test cases, each of which corresponds to a directed graphآ G. Each test case starts with an integer numberآ v, denoting the number of vertices ofآ G=(V,E), where the vertices will be identified by the integer
numbers in the setآ V={1,…,v}. You may assume thatآ 1<=v<=5000. That is followed by a non-negative integerآ eآ and, thereafter,آ eآ pairs of vertex identifiersآ v1,w1,…,ve,weآ with
the meaning thatآ (vi,wi)âˆˆE. There are no edges other than specified by these pairs. The last test case is followed by a zero.

Output

For each test case output the bottom of the specified graph on a single line. To this end, print the numbers of all nodes that are sinks in sorted order separated by a single space character. If the bottom is empty, print an empty line. Sample Input

```3 3
1 3 2 3 3 1
2 1
1 2
0
```

Sample Output

```1 3
2
```

Source

```#include<cstdio>
include<cstdlib>
include<algorithm>
include<functional>
include<cstring>
include<iostream>
using namespace std;
define MAXN (5000+10)
define MAXM (1000000+10)
int n,m,h[MAXN],t[MAXN],dfs[MAXN],tim,kind,s[MAXN],tot;
bool b[MAXN];
int edge[MAXM],next[MAXM],pre[MAXN],size;
int x[MAXM],y[MAXM],numk[MAXN];
{
edge[++size]=v;
next[size]=pre[u];
pre[u]=size;
}
void tar(int u)
{
dfs[u]=t[u]=++tim;b[u]=1;s[++tot]=u;
for (int p=pre[u];p;p=next[p])
{
int &v=edge[p];
if (!b[v]) tar(v),dfs[u]=min(dfs[u],dfs[v]);
else if (!h[v]) dfs[u]=min(dfs[u],t[v]);  //ن؟‌è¯پوŒ‡هگ‘ç¥–ه…ˆ
}
if (dfs[u]==t[u])
{
kind++;
while (s[tot]!=u) h[s[tot--]]=kind,numk[kind]++;
h[s[tot--]]=kind;numk[kind]++;
`}   `
}
int outdegree[MAXN];
int main()
{
while (scanf("%d",&n)&&n)
{
scanf("%d",&m);
tot=size=tim=kind=0;
memset(h,0,sizeof(h));
memset(t,0,sizeof(t));
memset(dfs,0,sizeof(dfs));
memset(s,0,sizeof(s));
memset(pre,0,sizeof(pre));
memset(b,0,sizeof(b));
memset(numk,0,sizeof(numk));
memset(outdegree,0,sizeof(outdegree));
```    for (int i=1;i&lt;=m;i++)
{
scanf(&quot;%d%d&quot;,&amp;x[i],&amp;y[i]);
}
for (int i=1;i&lt;=n;i++) if (!b[i]) tar(i);```
//      for (int i=1;i<=n;i++) cout<<h[i]<<' ';cout<<endl;
for (int i=1;i<=m;i++)
{
if (h[x[i]]^h[y[i]]) outdegree[h[x[i]]]++;
}
/
int ans=0;
for (int i=1;i<=kind;i++)
if (!outdegree[i]) ans+=numk[i];
cout<<ans<<endl;
/
bool flag=0;
for (int i=1;i<=n;i++)
if (!outdegree[h[i]])
{
if (flag) printf(" ");else flag=1;printf("%d",i);
}
```//  cout&lt;&lt;ans&lt;&lt;endl;
cout&lt;&lt;endl;
}
return 0;```
}

```