hdu 3594 強連通分量加環

hdu 3594 強連通分量加環

傳送門：Cactus

判斷給定的有向圖是否滿足 1.強連通 2 每一條邊屬於且僅屬於一個環？YES：NO

存在有兩種情況（yy一下）

1.他的子節點在棧中

2.他的子節點的最早的時間戳不是他

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define N 20005
stacksta;
vectormp[N];
int dfn[N];
int low[N];
int InStack[N];
int indexx,number;
int n, m;
int id[N];
int cnt[N];
int flag ;

void tarjan(int u)
{
    InStack[u] = 1;
    low[u] = dfn[u] = ++ indexx;
    sta.push(u);

    for (int i = 0; i < mp[u].size(); ++ i)
    {
        int t = mp[u][i];
        if (dfn[t] == 0)
        {
            tarjan(t);
            if(dfn[u]!=low[t]) cnt[u]++ ;//在如果t的祖先不是u的話，肯定要加一個環的，
            low[u] = min(low[u], low[t]);
        }
        else if (InStack[t] == 1)
        {
           cnt[u]++;//想了一下在這不用加判斷的，因為既然在這訪問到了，說明他肯定存在一個環
            low[u] = min(low[u], dfn[t]);
        }
        if(cnt[u]>1) flag =1;
    }

    if (low[u] == dfn[u])
    {
        ++ number;
        while (!sta.empty())
        {
            int v = sta.top();
            sta.pop();
            id[v]=number;
            InStack[v] = 0;
            if (v == u)
                break;
        }
    }
}

int main()
{
        int T;
        scanf("%d",&T);
        while(T--){
                flag =0;
            memset(dfn, 0, sizeof(dfn));
            memset(low, 0, sizeof(low));
            memset(InStack, 0, sizeof(InStack));
            memset(cnt,0,sizeof(cnt));
            indexx = number = 0;
            scanf("%d",&n);
            for (int i = 1; i <= n; ++ i)
            {
                mp[i].clear();
            }
            while(!sta.empty())
                sta.pop();
            int a,b;
            while(scanf("%d%d",&a,&b),a+b)
            {
                mp[a+1].push_back(b+1);
            }
            for(int i=1; i<=n; i++)
                if(!dfn[i])
                    tarjan(i);
            if(number>1)
            {
                printf("NO\n");
                continue;
            }
            else {
                if(flag) puts("NO");
                else puts("YES");
            }
        }
    }