The Bottom of a Graph

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 9779		Accepted: 4063

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=(e₁,...,e_n) be a sequence of length n of edges e_i∈E such that e_i=(v_i,v_i+1) for a sequence of vertices (v₁,...,v_n+1). Then p is called a path from vertex v₁ to vertex v_n+1 in Gand we say that v_n+1 is reachable from v₁, writing (v₁→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., bottom(G)={v∈V|∀w∈V:(v→w)⇒(w→v)}. You have to calculate the bottom of certain graphs.

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 v₁,w₁,...,v_e,w_e with the meaning that (v_i,w_i)∈E. There are no edges other than specified by these pairs. The last test case is followed by a zero.

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.

3 3

1 3 2 3 3 1

2 1

1 2

0

1 3

2
题意:给定一幅有向图,若某点所能到达的点也能到达其本身，那么这个点为sink。由小到大输出sink.
思路:有向图缩点得到一棵树,答案为构成叶子（出度为0）结点的连通分量。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

const int MAXN=;

vector<int> mp[MAXN];

int n,m;

int dfn[MAXN],low[MAXN],time;

int stack[MAXN],top;

bool ins[MAXN];

int belong[MAXN],cnt;

void dfs(int u)

{

    dfn[u]=low[u]=++time;

    stack[top++]=u;

    ins[u]=true;

    for(int i=;i<mp[u].size();i++)

    {

        int v=mp[u][i];

        if(!dfn[v])

        {

            dfs(v);

            low[u]=min(low[u],low[v]);

        }

        else if(ins[v])    low[u]=min(low[u],dfn[v]);

    }

    if(dfn[u]==low[u])

    {

        int v;

        cnt++;

        do{

            v=stack[--top];

            belong[v]=cnt;

            ins[v]=false;

        }while(u!=v);

    }

}

int deg[MAXN];

bool flag[MAXN];

void solve()

{

    /*

    for(int i=1;i<=n;i++)

        printf("%d\n",belong[i]);*/

    for(int i=;i<=n;i++)

        for(int j=;j<mp[i].size();j++)

        {

            int v=mp[i][j];

            if(belong[i]!=belong[v])

            {

                deg[belong[i]]++;

            }

        }

    for(int i=;i<=cnt;i++)

        if(deg[i]==)

            flag[i]=true;

    for(int i=;i<=n;i++)

        if(flag[belong[i]])

            printf("%d ",i);

    printf("\n");

}

int main()

{

    while(scanf("%d",&n)!=EOF&&n)

    {

        scanf("%d",&m);

        memset(dfn,,sizeof(dfn));

        memset(low,,sizeof(low));

        memset(ins,false,sizeof(ins));

        memset(deg,,sizeof(deg));

        memset(flag,false,sizeof(flag));

        top=;

        time=;

        cnt=;

        for(int i=;i<=n;i++)

            mp[i].clear();

        for(int i=;i<m;i++)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            mp[u].push_back(v);

        }

        for(int i=;i<=n;i++)

            if(!dfn[i])

                dfs(i);

        solve();

    }

}

#include"cstdio"

#include"cstring"

#include"vector"

using namespace std;

const int MAXN=;

vector<int> G[MAXN];

vector<int> rG[MAXN];

vector<int> vs;

int V,E;

int cpnt[MAXN];

int vis[MAXN];

void dfs(int u)

{

    vis[u]=;

    for(int i=;i<G[u].size();i++)

        if(!vis[G[u][i]])    dfs(G[u][i]);

    vs.push_back(u);

}

void rdfs(int u,int k)

{

    cpnt[u]=k;

    vis[u]=;

    for(int i=;i<rG[u].size();i++)

        if(!vis[rG[u][i]])    rdfs(rG[u][i],k);

}

void scc()

{

    memset(vis,,sizeof(vis));

    for(int i=;i<=V;i++)

        if(!vis[i])    dfs(i);

    memset(vis,,sizeof(vis));

    int k=;

    for(int i=vs.size()-;i>=;i--)

        if(!vis[vs[i]])    rdfs(vs[i],k++);

}

int deg[MAXN];

void solve()

{

    scc();

    for(int i=;i<=V;i++)

    {

        for(int j=;j<G[i].size();j++)

        {

            int to=G[i][j];

            if(cpnt[i]!=cpnt[to])

            {

                deg[cpnt[i]]++;

            }

        }

    }

    int flag=;

    for(int i=;i<=V;i++)

    {

        if(deg[cpnt[i]]==)

        {

            if(flag==)

            {

                printf("%d",i);

                flag=;

            }

            else

            {

                printf(" %d",i);

            }

        }

    }

    printf("\n");

}

int main()

{

    while(scanf("%d",&V)!=EOF&&V)

    {

        scanf("%d",&E);

        vs.clear();

        memset(cpnt,,sizeof(cpnt));

        memset(deg,,sizeof(deg));

        for(int i=;i<=V;i++)

        {

            G[i].clear();

            rG[i].clear();

        }

        for(int i=;i<E;i++)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            G[u].push_back(v);

            rG[v].push_back(u);

        }

        solve();

    }

    return ;

}