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 graphG. 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 setV={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

题意:n个点 m个边 求染色缩点后 出度为零的点 然后将这些点正序输出

因为刷到了lca的题然后特意跑回来补一下tajan的知识点

挺好理解的 就是正序dfs一次将所有点标号dfn[u]  然后回溯的时候取一下最小的dfn[v]为low[u]

如果dfn[u]==low[u]那么代表有一个强联通分量 至于为什么，泥猜。。。

正规的解释在这里

然后先放一下最原始的tarjan模板（不带染色缩点

void Tarjan(int u)//此代码仅供参考
{
    vis[u]=1;
    low[u]=dfn[u]=cnt++;
    for(int i=0;i<mp[u].size();i++)
    {
        int v=mp[u][i];
        if(vis[v]==0)Tarjan(v);
        if(vis[v]==1)low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u])
    {
        sig++;
    }
}

这个题的题解在这

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <algorithm>
#define maxn 5000+5
using namespace std;
typedef long long int ll;
int n,m;
int vis[maxn],dfn[maxn],low[maxn],stac[maxn],tt,cnt,sig;
int degree[maxn],color[maxn];
vector<int>G[maxn];
void init(){
    memset(degree,0,sizeof(degree));
    memset(color,0,sizeof(color));
    memset(stac,0,sizeof(stac));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)G[i].clear();
    tt=-1,cnt=1,sig=0;
}
void Tarjan(int u)
{
    vis[u]=1;
    low[u]=dfn[u]=cnt++;
    stac[++tt]=u;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(vis[v]==0)Tarjan(v);
        if(vis[v]==1)low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u])
    {
        sig++;
        do
        {
            color[stac[tt]]=sig;
            vis[stac[tt]]=-1;
        }
        while(stac[tt--]!=u);
    }
}
int main(){
    while(scanf("%d",&n)&&n){
        scanf("%d",&m);
        init();
        for(int i=0;i<m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
        }
        for(int i=1;i<=n;i++){
            if(vis[i]==0)
            Tarjan(i);
        }
        for(int i=1;i<=n;i++){
            for(int j=0;j<G[i].size();j++){
                int v=G[i][j];
                if(color[i]!=color[v]){
                    degree[color[i]]++;
                }
            }
        }
        vector<int>ans;
        for(int i=1;i<=n;i++){
            if(degree[color[i]]==0)
                ans.push_back(i);
        }
        sort(ans.begin(),ans.end());
        for(int i=0;i<ans.size();i++){
            printf("%d",ans[i]);
            if(i!=ans.size()-1)printf(" ");
            else printf("\n");
        }
        //cout<<233<<endl;
    }
    return 0;
}