CUGB图论专场2：The Bottom of a Graph 强连通Tarjan算法

H - The Bottom of a Graph

Time Limit:3000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u

Submit  Status

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=(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  G and 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.

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  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.

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

题意：求这样的点：从u可以到v，从v也可以到u的所有点，并且是最底部的，因为是有向图，再根据样例结果，所以Bottom应该是出度为0的点，就是缩点后求出度为0的点。

思路：求强连通后缩点，然后求出度为0 的点就行，出度为0的点在强连通之前可能有多个点的，所以在Tarjan中需要把强连通的那些点记录下来，以便在求出度为0的点使用。

感想：这题WA了十多发，从昨晚做一直到现在都是Wa，搞不明白是什么回事。还以为是边界错了，但是都改了也不对。然后刚才一句一句的看，才发现写代码的时候，在Tarjan算法中把min写成了max，然后LOW数组就错了。靠！！！！！细节搞死人啊，手误就误了一天了！！！！

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define MM 10002
#define MN 5005
#define INF 168430090
using namespace std;
typedef long long ll;
int n,m,cnt,tem,Count,DFN[MN],LOW[MN],od[MN],vis[MN],suo[MN],q2[MN];
vector<int>q[MN],p[MN];
void tarjan(int u)
{
    int j,v;
    DFN[u]=LOW[u]=++cnt;
    vis[u]=1;
    q2[++tem]=u;
    for(j=0; j<q[u].size(); j++)
    {
        v=q[u][j];
        if(!DFN[v])
        {
            tarjan(v);
            LOW[u]=min(LOW[u],LOW[v]); //把min写成了max然后导致错了十多发
        }
        else if(vis[v]&&DFN[v]<LOW[u])
            LOW[u]=DFN[v];
    }
    if(DFN[u]==LOW[u])
    {
        Count++;
        do
        {
            v=q2[tem--];
            vis[v]=0;
            p[Count].push_back(v); //连通结点记录下来
            suo[v]=Count; //缩点，属于同一个强连通则缩成新的一个结点
        }
        while(v!=u);
    }
}
void solve()
{
    int v,i,j;
    Count=cnt=tem=0;
    mem(DFN,0);
    for(i=1; i<=n; i++)
        if(!DFN[i]) tarjan(i);
    for(i=1; i<=n; i++)  //此循环在缩点的基础上，如果需要重新建图就可以重新建图，这里不需要重新建图
        for(j=0; j<q[i].size(); j++)
        {
            v=q[i][j];
            if(suo[v]!=suo[i])
                od[suo[i]]++; //不属于同一个强连通
        }
}
int main()
{
    int i,j,u,v,sum;
    while(sca(n)&&n)
    {
        sca(m);
        set<int>s;
        set<int>::iterator it;
        for(i=0; i<=n; i++) q[i].clear(),p[i].clear();
        mem(od,0);
        mem(LOW,0);
        mem(vis,0);
        mem(suo,0);
        for(i=0; i<m; i++)
        {
            scanf("%d%d",&u,&v);
            q[u].push_back(v);
        }
        solve();
        for(i=1; i<=Count; i++)
            if(od[i]==0)  //如果出度为0，即从u可以到v，v也可以到u，题目是这个意思，在图论中就是缩点后出度为0
            {
                for(j=0; j<p[i].size(); j++)
                    s.insert(p[i][j]); //因为set自动从小到大排序，所以引用
            }
        for(it=s.begin(),sum=0; it!=s.end(); it++)
        {
            cout<<*it;
            sum++;
            if(sum<s.size()) cout<<' ';
        }
        cout<<endl;
    }
    return 0;
}