[poj 2553]The Bottom of a Graph[Tarjan強連通分量]

題意:

求出度為0的強連通分量.

思路:

縮點

具體有兩種實現:

1.遍歷所有邊, 邊的兩端點不在同一強連通分量的話, 將出發點所在強連通分量出度+1.

#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
//0.03s  4856K
const int MAXN = 5005;
struct Pool
{
    int pre, v;
}p[MAXN*100];//適當開
int num,head[MAXN];
int low[MAXN];
int dfn[MAXN],Index;
int id[MAXN],size;
bool vis[MAXN];
stack<int> s;
int n,m;
int deg[MAXN];

void clear()
{
    num = 1;//求鄰邊,異或方便,從2開始
    memset(head,0,sizeof(head));
    memset(vis,false,sizeof(vis));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(deg,0,sizeof(deg));
    Index = size = 0;
    while(!s.empty())   s.pop();
}

void add(int u, int v)
{
    p[++num].v = v;
    p[num].pre = head[u];//pre為0,說明該邊為第一條邊
    head[u] = num;
}

void Tarjan(int u)
{
    dfn[u] = low[u] = ++Index;
    s.push(u);
    vis[u] = true;
    for(int tmp = head[u],k;k = p[tmp].v,tmp; tmp = p[tmp].pre)
    {
        if(!dfn[k])
        {
            Tarjan(k);
            low[u] = min(low[u], low[k]);
        }
        else if(vis[k])
        {
            low[u] = min(low[u], low[k]);
            ///low[u] = min(low[u], dfn[k]);這兩種都可以啦~
        }
    }
    
    if(dfn[u]==low[u])
    {
        size++;
        int k;
        do
        {
            k = s.top(); s.pop();
            vis[k] = false;
            id[k] = size;
        }while(k!=u);
    }
}

void cal()
{
    for(int i=1;i<=n;i++)
    {
        for(int tmp = head[i],k;k = p[tmp].v,tmp; tmp = p[tmp].pre)
        {
            if(id[i]!=id[k])
            {
                deg[id[i]]++;
            }
        }
    }
}

int main()
{
    while(scanf("%d",&n),n)
    {
        clear();
        scanf("%d",&m);
        for(int i=0,u,v;i<m;i++)
        {
            scanf("%d %d",&u,&v);
            add(u,v);
        }
        for(int i=1;i<=n;i++)
        {
            if(!dfn[i])
                Tarjan(i);
        }
        cal();
        bool blank = false;
        for(int i=1;i<=n;i++)
        {
            if(!deg[id[i]])
            {
                if(!blank)
                {
                    printf("%d",i);
                    blank = true;
                }
                else
                    printf(" %d",i);
            }
        }
        printf("\n");
    }
}

2. 在dfs的過程中,標記出度.

設當前節點為u

若訪問到了黑色點, 則出度不為0.

若訪問到了灰色點, 正常

若訪問到了白色點, 則這個白色點k

若被搜索之後屬於同一強連通分量,則low[ k ] < dfn[ k ] (注意,並不一定有 low[ k ] < low[ u ], 因為k可能連接到了較靠後的灰色點,而u之前已經被較靠前的灰色點更新過).

若被搜索之後屬於另一個(不同於u的)強連通分量, 那麼可以證明 low[ k ] == dfn[ k ], 即k一定是入口.

黑體字的兩條就包括了所有出度非0的情況. 據此來實現縮點.

#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
//0.03s   4812K
const int MAXN = 5005;
struct Pool
{
    int pre, v;
}p[MAXN*100];//適當開
int num,head[MAXN];
int low[MAXN];
int dfn[MAXN],Index;
int id[MAXN],size;
bool vis[MAXN];
stack<int> s;
int n,m;
bool black[MAXN];
bool odd[MAXN];


void clear()
{
    num = 1;
    memset(head,0,sizeof(head));
    memset(vis,false,sizeof(vis));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(black,false,sizeof(black));
    memset(odd,false,sizeof(odd));
    Index = size = 0;
    while(!s.empty())   s.pop();
}

void add(int u, int v)
{
    p[++num].v = v;
    p[num].pre = head[u];
    head[u] = num;
}

void Tarjan(int u)
{
    dfn[u] = low[u] = ++Index;
    s.push(u);
    vis[u] = true;
    for(int tmp = head[u],k;k = p[tmp].v,tmp; tmp = p[tmp].pre)
    {
        if(!dfn[k])
        {
            Tarjan(k);
            if(low[k]==dfn[k])///如果訪問到了白色點,那麼新的強連通分量的入口一定在這個點
                black[u] = true;
            low[u] = min(low[u], low[k]);
        }
        else if(vis[k])
        {
            low[u] = min(low[u], low[k]);
        }
        else
            black[u] = true;
    }///low只是指"當前找到的強連通分量的進入時間戳"
    ///而非"極大強連通分量"的進入時間戳.但是肯定小於自己的時間戳(恰好是進入點的話就是等於).
    if(dfn[u]==low[u])
    {
        size++;
        int k;
        do
        {
            k = s.top(); s.pop();
            vis[k] = false;
            id[k] = size;
            if(black[k])
                odd[size] = true;
        }while(k!=u);
    }
}

int main()
{
    while(scanf("%d",&n),n)
    {
        clear();
        scanf("%d",&m);
        for(int i=0,u,v;i<m;i++)
        {
            scanf("%d %d",&u,&v);
            add(u,v);
        }
        for(int i=1;i<=n;i++)
        {
            if(!dfn[i])
                Tarjan(i);
        }
        bool blank = false;
        for(int i=1;i<=n;i++)
        {
            if(!odd[id[i]])
            {
                if(!blank)
                {
                    printf("%d",i);
                    blank = true;
                }
                else
                    printf(" %d",i);
            }
        }
        printf("\n");
    }
}