A115471.双色序判定 题解

#include<bits/stdc++.h>
using namespace std;
int t,g[105][105],c[105],p[105],a[105],deg[105];
int main(){
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>a[i];
            p[a[i]]=i;
            deg[i]=0;
            c[i]=-1;
        }
        for(int i=0;i<n-1;i++){
            g[i][++deg[i]]=i+1,g[i+1][++deg[i+1]]=i;
        }
        for(int v=1;v<n;v++){
            int u=p[v],w=p[v+1];
            g[u][++deg[u]]=w;g[w][++deg[w]]=u;
        }
        bool ok=true;
        for(int s=0;s<n&&ok;s++){
            if(c[s]!=-1){
                continue;
            }
            int q[105],h=0,t=0;q[t++]=s;c[s]=0;
            while(h<t&&ok){
                int u=q[h++];
                for(int i=1;i<=deg[u];i++){
                    int v=g[u][i];
                    if(c[v]==-1){
                        c[v]=c[u]^1;
                        q[t++]=v;
                    }else if(c[v]==c[u]){
                        ok=false;
                    }
                }
            }
        }
        cout<<(ok?"YES":"NO")<<endl;
    }
}