首页 > 其他 > 详细

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

时间:2014-02-19 23:02:47      阅读:433      评论:0      收藏:0      [点我收藏+]

H - The Bottom of a Graph
Time Limit:3000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u

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.bubuko.com,布布扣

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;
}


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

原文:http://blog.csdn.net/u011466175/article/details/19483085

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!