[CF 521E] Cycling City

作法：

首先當然是把每個連通塊分開看，如果其中一塊有解就是有解，因此以下假定圖連通。如果這張圖裡面沒有環的話，那顯然就沒有解。如果有環的話，那麼就代表如果存在環上的兩個點 A 和 B，使得 A 可以經過一連串不在環上的點走到 B 的話，A 和 B 之間就存在三條路徑。因此可以得到：存在滿足題目要求的三條路徑若且唯若這張圖不是仙人掌圖( cactus graph )。之前我就有遇過有向圖版本的仙人掌問題( TIOJ 1484 ) ( 題解 )，作法是考慮 DFS 樹，那麼這裡應該也差不多。

因此一樣考慮DFS樹，如果樹上沒有回邊，那就代表原圖裡沒有圈，此時不可能有解。反之我們會找到一條回邊，假設為 B -> A 好了，那麼就可以把樹上的從 A 到 B 的這段路徑上的所有邊都標記為「被 A 和 B 所有」了，因為如果之後又找到了另一條回邊 D -> C ，其中樹上的從 C 走到 D 的路徑會和從 A 走到 B 的路徑有交集，那麼這樣就可以產生三條不相交的路徑了（可以自己畫畫看）。因此當我們在之後找到一條回邊 D->C ， 並準備要把所有 C 到 D 之間的邊都標記為「被 C 和 D 所有」的時候，發現有一條邊早就被標記成 「被 A 和 B」所有的時候，就代表找到一個解了。因此剩下的工作就是把解印出來，首先確定三條路徑的起點和終點，討論一下各種情形可以得到起點其實會是 B 和 D 的LCA，而終點則是 A 和 C 中深度比較深的那一個，確認起點和終點之後，剩下只需要一個能夠獲得「從 X 走到 Y 的路徑上依序經過的點們」的函式就可以了，並且因為每次我們需要的路徑都會長的像「自己走到某個自己的祖先」或是「自己走到某個自己的子孫」，因此這個函式就可以用「一直沿著父親往上跳」的方法實作。

另外我覺得官方解的作法比我的簡潔很多，可以參考看看，或是參考dreamoon的題解XD。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10 ;
 
void print(const vector<int> &u)
{
    printf("%d",u.size()) ;
    for(auto i : u) printf(" %d",i) ;
    printf("\n") ;
}
 
vector<int> v[maxn] ;
int fa[maxn] ;
int lev[maxn] ;
int up[maxn],dn[maxn] ;
int A,B,C,D ; /// back edge : B->A & D->C
 
bool dfs(int x,int l)
{
    lev[x]=l ;
    for(auto i : v[x]) if(i!=fa[x])
    {
        if(lev[i]==-1)
        {
            fa[i]=x ;
            if(dfs(i,l+1)) return 1 ;
        }
        else if(lev[i]>lev[x]) continue ;
        else for(int j=x;j!=i;j=fa[j])
        {
            if(up[j])
            {
                A=up[j] ; B=dn[j] ;
                C=i ; D=x ;
                return 1 ;
            }
            up[j]=i ; dn[j]=x ;
        }
    }
    return 0 ;
}
 
int LCA(int x,int y)
{
    while(lev[x]<lev[y]) y=fa[y] ;
    while(lev[x]>lev[y]) x=fa[x] ;
    while(x!=y) x=fa[x] , y=fa[y] ;
    return x ;
}
 
vector<int> tmp ;
void getpath(int x,int y,vector<int> &ret)
{
    tmp.clear() ;
    if(x==y) tmp.push_back(x) ;
    else if(lev[x]>lev[y])
        for(int i=x;;i=fa[i])
    {
        tmp.push_back(i) ;
        if(i==y) break ;
    }
    else for(int i=y;;i=fa[i])
    {
        tmp.push_back(i) ;
        if(i==x)
        {
            reverse(tmp.begin(),tmp.end()) ;
            break ;
        }
    }
    for(auto i : tmp) ret.push_back(i) ;
}
 
vector<int> ans ;
bool solve(int x)
{
    fa[x]=-1 ;
    if(dfs(x,1))
    {
        printf("YES\n") ;
        int st=LCA(B,D) , ed= (lev[C]>lev[A] ? C : A) ;
        getpath(st,ed,ans) ;
        print(ans) ; ans.clear() ;
        getpath(st,B,ans) ;
        getpath(A,ed,ans) ;
        print(ans) ; ans.clear() ;
        getpath(st,D,ans) ;
        getpath(C,ed,ans) ;
        print(ans) ; return 1 ;
    }
    return 0 ;
}
 
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    while(m--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
    memset(lev,-1,sizeof(lev)) ;
    for(int i=1;i<=n;i++) if(lev[i]==-1 && solve(i))
        return 0 ;
    printf("NO\n") ;
}