[TIOJ 1484] 仙人掌

作法：

考慮這張圖以任意一個點為根的DFS樹，第一個因為他要是強連通的，所以圖裡不能有橋，也就是如果記 lev[ x ] 代表 DFS 時每個節點的深度， low[ x ] 代表每個節點可以走到的 lev 的最小的值，那麼要有 low[ v ] <= lev[ u ] ，其中 v 是 u 的子節點。然後可以得到這顆樹上沒有交錯邊( cross edge )，如果有的話會造成有一條邊被兩個圈用到( 在這裡我們也把從祖先指向子孫的邊叫交錯邊，都是不能出現的邊 )。最後考慮 u 到他祖先的這條邊，如果要他不被用到兩次的話，就必須要有以 u 為起點的回邊數量 + u 的可以走到深度 < lev[ u ] 的子節點數量 < 2 。只要在DFS的時候判斷這些條件就可以了。

對了，記得最後還要判是否每個點都被走到了，他竟然佔了測資的一大部分QQ

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
vector<int> v[maxn] ;
 
int vis[maxn] ;
int lev[maxn],low[maxn] ;
 
bool dfs(int x,int l)
{
    lev[x]=low[x]=l ;
    vis[x]=-1 ;
    int num=0 ;
    for(auto i : v[x])
    {
        if(vis[i]==1) return 0 ;
        else if(vis[i]==-1) num++ , low[x]=min(low[x],lev[i]) ;
        else
        {
            if(!dfs(i,l+1)) return 0 ;
            low[x]=min(low[x],low[i]) ;
            if(low[i]>lev[x]) return 0 ;
            if(low[i]<lev[x]) num++ ;
        }
    }
    vis[x]=1 ;
    return num<2 ;
}
 
main()
{
    int T ; scanf("%d",&T) ;
    while(T--)
    {
        int n,m ; scanf("%d%d",&n,&m) ;
        for(int i=0;i<n;i++) v[i].clear() ;
        while(m--)
        {
            int x,y ; scanf("%d%d",&x,&y) ;
            if(x!=y) v[x].push_back(y) ;
        }
        fill(vis,vis+n,0) ;
        if(!dfs(0,0)) printf("NO\n") ;
        else
        {
            bool ok=1 ;
            for(int i=0;i<n;i++) if(!vis[i])
                {ok=0 ; break ;}
            if(!ok) printf("NO\n") ;
            else printf("YES\n") ;
        }
    }
}