排序+并查集——cf1213F

红太狼 2023-10-11 09:04 40阅读 0赞

/*
    有向边(pi,pi+1)，形成链后进行dfs,求出dfs序 
    一个联通块内的元素必须是同一个字符，如果最后的联通块个数<k,说明不行 
    */
    #include<bits/stdc++.h>
    using namespace std;
    #define N 200005
    int n,k,p[N],q[N];
    
    int rk1[N],rk2[N];
    
    struct Node{
        int id,rk;}a[N],b[N];
    int cmp1(Node a,Node b){
        return a.rk<b.rk;}
    int cmp2(Node a,Node b){
        return a.rk<b.rk;}
    
    int F[N];
    int find(int x){
        return F[x]==x?x:F[x]=find(F[x]);
    }
    void bing(int u,int v){
        int f1=find(u),f2=find(v);
        if(f1==f2)return;
        else F[f1]=f2;
    }
    int ans[N];
    int main(){
        cin>>n>>k;
        for(int i=1;i<=n;i++)cin>>p[i];
        for(int i=1;i<=n;i++)cin>>q[i];
        for(int i=1;i<=n;i++)rk1[p[i]]=i,rk2[q[i]]=i;
        
        for(int i=1;i<=n;i++)a[i].id=i,a[i].rk=rk1[i];
        sort(a+1,a+1+n,cmp1);//按照rk1升序排序
        
        for(int i=1;i<=n;i++)b[i].id=i,b[i].rk=rk2[i];
        sort(b+1,b+1+n,cmp2);//按照rk2升序排列 
        
        for(int i=1;i<=n;i++)F[i]=i; 
        
        int pos=1,vis[N];
        memset(vis,0,sizeof vis);
        for(int i=1;i<=n;i++)if(!vis[b[i].id]){
            //直到a[pos].id==b[i].id
            pos=max(pos,i);
            while(a[pos].id!=b[i].id){
                vis[a[pos].id]=1;
                bing(b[i].id,a[pos].id);
                pos++; 
            }
            vis[b[i].id]=1;
        }
        //求联通块个数联通块
        int tot;
        for(int i=1;i<=n;i++){
            find(i);
            if(F[i]==i)tot++;
        }
        if(tot<k){puts("NO");return 0;}
        
        //染色
        memset(vis,0,sizeof vis); 
        int c=0;
        for(int i=1;i<=n;i++){
            if(!vis[F[a[i].id]]){
                ans[a[i].id]=min(26,++c);
                vis[F[a[i].id]]=1;
            }
            else ans[a[i].id]=min(26,c);
        }
        
        puts("YES");
        for(int i=1;i<=n;i++)
            cout<<(char)(ans[i]+'a'-1);
        puts("");
    }

转载于:https://www.cnblogs.com/zsben991126/p/11508882.html