POJ 2553 The Bottom of a Graph 强连通分量

链接：http://poj.org/problem?id=2553

题意：题意读起来压力大，是找到自己能找到并且还能找到自己，并且在图的底部的点。

思路：找到出度为零的强连通分量，用Tarjan缩点。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <ctype.h>
#include <algorithm>
#include <string>
#define PI acos(-1.0)
#define maxn 5500
#define INF 1<<25
#define MAX 0x7fffffff
#define mem(a,b) memset(a,b,sizeof(a))
#define f(i,a,b) for(i=a;i<b;i++)
typedef long long ll;
using namespace std;
struct Edge
{
    int v;
    int next;
} edge[maxn*maxn];
stack <int> S;
int head[maxn],dfn[maxn],low[maxn],ins[maxn],ou[maxn],belong[maxn];
int top,cnt,t,jud,to;
int init()
{
    mem(head,-1);
    mem(ins,0);
    mem(dfn,0);
    mem(low,0);
    mem(ou,0);
    mem(belong,0);
    top=t=cnt=jud=0;
}
int add_edge(int u,int v)
{
    edge[top].v=v;
    edge[top].next=head[u];
    head[u]=top++;
}
int tarjan(int u)
{
    dfn[u]=low[u]=cnt++;
    S.push(u);
    ins[u]=1;
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        int v=edge[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(dfn[v]<low[u]&&ins[v])
        {
            low[u]=dfn[v];
        }
    }
    if(dfn[u]==low[u])
    {
        t++;
        int to;
        do
        {
            to=S.top();
            S.pop();
            belong[to]=t;
            ins[to]=0;
        }
        while(to!=u);
    }
}
int main()
{
    int tot,tt;
    while(scanf("%d",&tot))
    {
        init();
        while(!S.empty())
        {
            S.pop();
        }
        if(!tot)
            return 0;
            scanf("%d",&tt);
        for(int i=1;i<=tt;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            add_edge(a,b);
        }
        for(int i=1; i<=tot; i++)
        {
            if(!dfn[i])
                tarjan(i);
        }

        for(int i=1;i<=tot;i++)
        for(int j=head[i]; j!=-1; j=edge[j].next)
        {
            int s=edge[j].v;
            if(belong[i]!=belong[s])
            {
                ou[belong[i]]++;
            }
        }
        for(int j=1;j<=tot;j++)
        {
            if(!ou[belong[j]])
            {
                if(!jud)
                {
                    printf("%d",j);
                    jud=1;
                }
                else printf(" %d",j);
            }
        }
        printf("\n");
    }
}

POJ 2553 The Bottom of a Graph 强连通分量,布布扣,bubuko.com

POJ 2553 The Bottom of a Graph 强连通分量

原文：http://blog.csdn.net/ooooooooe/article/details/20912097