HDU 3594 Cactus （仙人掌圖、Tarjan）

Description

1. It is a Strongly Connected graph.
2. Each edge of the graph belongs to a circle and only belongs to one circle.

We call this graph as CACTUS.

There is an example as the figure above. The left one is a cactus, but the right one isn’t. Because the edge (0, 1) in the right graph belongs to two circles as (0, 1, 3) and (0, 1, 2, 3).

Input

The input consists of several test cases. The first line contains an integer T (1<=T<=10), representing the number of test cases.

For each case, the first line contains a integer n (1<=n<=20000), representing the number of points.

The following lines, each line has two numbers a and b, representing a single-way edge (a->b). Each case ends with (0 0).

Notice: The total number of edges does not exceed 50000.

Output

For each case, output a line contains “YES” or “NO”, representing whether this graph is a cactus or not.

Sample Input

2
4
0 1
1 2
2 0
2 3
3 2
0 0
4
0 1
1 2
2 3
3 0
1 3
0 0      

Sample Output

YES
NO      

題意

給出一張有向圖，判斷其是否是仙人掌圖。

思路

在解決這道題之前我們首先要知道什麼是仙人掌圖。

直覺的說，仙人掌圖就是一個一個的圈直接“粘”在一起的圖，圈之間沒有公共邊。

我們主要根據其以下三點性質來做出判斷：

1. 仙人掌圖的 DFS 樹沒有橫向邊
2. ​

   ​Low(u)<=DFN(v)​

   ​ （u 是 v 的兒子）
3. 設某個點 v 有 a(v) 個兒子的 Low 值小于 DFN(v) ，同時 v 自己有 b(v) 條逆向邊，那麼​

   ​a(v)+b(v)<2​

   ​

AC 代碼

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<map>
using namespace std;

const int maxn = 51000;
int DFN[maxn];          //記錄搜尋到該點的時間
int LOW[maxn];          //記錄目前搜尋的強連通子圖搜尋樹的根節點
int Stack[maxn],Stop;   //工作棧
int Dindex;             //一個計數器，記錄通路節點的次序
bool instack[maxn];     //記錄目前點是否在棧中
bool ans;

struct node
{
    int to;
    int next;
} edge[maxn];
int head[maxn],tot,n;

void init()
{
    memset(head,-1,sizeof(head));
    memset(DFN,0,sizeof(DFN));
    memset(instack,false,sizeof(instack));
    tot=Dindex=Stop=0;
    ans=true;
}

void addedge(int u,int v)
{
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}

void tarjan(int i)
{
    DFN[i]=LOW[i]=++Dindex;
    instack[i]=true;
    Stack[++Stop]=i;
    int cnt=0;
    for(int k=head[i]; k!=-1; k=edge[k].next)
    {
        int j=edge[k].to;
        if (!DFN[j])    //如果鄰接的該點沒有被标記
        {
            tarjan(j);
            if (LOW[j]<LOW[i])  //如果鄰接點搜尋結束後LOW更小，說明在j中找到一個環，然後使環中所有LOW統一
                LOW[i]=LOW[j];
        }
        else if (instack[j] && DFN[j]<LOW[i])   //找到一個環
            LOW[i]=DFN[j];
        else if(!instack[j])    //第一條性質
        {
            ans=false;
            return;
        }
        if(LOW[j]>DFN[i])       //仙人掌第二條性質
        {
            ans=false;
            return;
        }
        if(DFN[j]<DFN[i]||(DFN[j]>DFN[i]&&LOW[j]<LOW[i]))   //仙人掌第三條性質
            cnt++;
    }
    if(cnt>1)
    {
        ans=false;
        return;
    }
    if (DFN[i]==LOW[i]) //相等說明i為強連通子圖搜尋樹的根節點
    {
        int top;
        do  //退棧
        {
            top=Stack[Stop--];
            instack[top]=false;
        }
        while (top!=i);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        init();
        cin>>n;
        while(true)
        {
            int a,b;
            cin>>a>>b;
            if(a==0&&b==0)break;
            addedge(a,b);
        }
        tarjan(0);
        cout<<(ans?"YES":"NO")<<endl;
    }
    return 0;
}