# 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 vv 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

Tarjen缩点统计出度。

```#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];
void addedge(int u,int v)
{
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;```
}

```