题解：P14480 化作彗星

· · 题解

曾经的我会做的题。

先判掉孤立点，接下来默认没有孤立点。

然后判掉 \forall i\in[1,n),f(a_i,a_{i+1})=0，因为你什么操作都做不了。而且若 \exists i\in[1,n)，f(a_i,a_{i+1})=1，那么你无论怎么做操作都做不到第一个条件，所以接下来默认 \exists i\in[1,n)，f(a_i,a_{i+1})=1 且 \exists i\in[1,n)，f(b_i,b_{i+1})=1。

先只考虑一个序列。设 u=a_i,v=a_{i+1} 满足 f(u,v)=1。对于每个 x 存在一个与其连边的 y，那么对于序列中一个子串都有 [u,v,x]\to[x,y,x]\to[x,u,v]。意味着 (u,v) 这条边可以乱跑。

更加具体地说，若存在 x,y,z 满足 f(x,y)=f(y,z)=1，那么 [u,v,x]\to[z,y,x]\to[z,u,v]\to[u,v,z]。所以我们可以让任意一个点 x 变成走两步走到的 z。

我们可以用并查集维护走 偶数 布能走到的点和走 奇数 步能走到的点。两个相邻的点若可以通过走 奇数 步走到一起，那么这两个点可以通过上面的操作凑成一条边。又因为一条边可以乱飞，我们就认为这两个点被删了。

我们用栈来维护这个过程，加入一个点的时候就和栈顶判断能否构成一对边，能就删栈顶，不能就加入当前点。最后合法的充分必要条件就是两个栈等价（即栈大小相同且对应点可以走 偶数 步互相到达）。

由于操作可逆，证明其充分性和必要性都是简单的，在这里我就不赘述了。

可能需要根据代码理解：

#include <bits/stdc++.h>
using namespace std;
const int N=4e5+10;
int n,m,q,d[N];
unordered_map<int,int> G[N];
struct FaC{
    int fa[N];
    void init(){for(int i=1;i<=n*2;i++) fa[i]=i;}
    int find(int x){return (fa[x]==x?x:fa[x]=find(fa[x]));}
    void merge(int x,int y){
        x=find(x),y=find(y);
        if(x>y) swap(x,y);
        fa[y]=x;
    }
}F;
void read(){
    cin>>m>>n>>q;
    F.init();
    int x,y;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        F.merge(x,y+n),F.merge(x+n,y);
        d[x]++,d[y]++;
        G[x][y]=G[y][x]=1;
    }
}
int len,a[N],b[N];
int topa,topb,sta[N],stb[N];
bool solve(int *a,int *b,int len){
    if(len<=0) return 1;
    int fl=0,fr;
    for(int i=1;i<=len;i++) if(a[i]!=b[i]) fl=1;
    if(fl==0) return 1;
    fl=fr=0;
    for(int i=1;i<len;i++){
        if(G[a[i]][a[i+1]]) fl=1;
        if(G[b[i]][b[i+1]]) fr=1;
    }
    if(fl==0 || fr==0) return 0;
    topa=topb=0;
    for(int i=1;i<=len;i++){
        if(topa && F.find(sta[topa]+n)==F.find(a[i])) topa--;
        else sta[++topa]=a[i];
        if(topb && F.find(stb[topb]+n)==F.find(b[i])) topb--;
        else stb[++topb]=b[i];
    }
    if(topa!=topb) return 0;
    for(int i=1;i<=topa;i++){
        if(F.find(sta[i])!=F.find(stb[i])) return 0;
    }
    return 1;
}
bool check(int *a,int *b,int len){
    int lst=0;
    for(int i=1;i<=len;i++){
        if(!d[a[i]] && d[b[i]]) return 0;
        if(d[a[i]] && !d[b[i]]) return 0;
    }
    for(int i=1;i<=len;i++) if(!d[a[i]]){
        if(a[i]!=b[i]) return 0;
    }
    for(int i=1;i<=len+1;i++) if(i==len+1 || !d[a[i]]){
        if(!solve(a+lst,b+lst,i-lst-1)) return 0;
        lst=i;
    }
    return 1;
}
void work(){
    while(q--){
        cin>>len;
        for(int i=1;i<=len;i++) cin>>a[i];
        for(int i=1;i<=len;i++) cin>>b[i];
        if(check(a,b,len)) cout<<"YES\n";
        else cout<<"NO\n";
    }
}
int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    read();
    work();
    cerr<<1.0*clock()/CLOCKS_PER_SEC<<'\n';
    return 0;
}