CodeForces 1213F (强联通分量分解+拓扑排序)

传送门

•题意

给你两个数组 p,q ，分别存放 1~n 的某个全排列；

让你根据这两个数组构造一个字符串 S，要求：

(1)$\forall i \in [1,n-1],S_{pi}\leq S _{pi+1}  ,\forall i \in [1,n-1],S_{qi} \leq S _{qi+1}$

(2)字符串 S 至少包含 k 个不同的小写字母；

•思路

类似于牛客第五场的H

不过由于这个不知道字母是什么，需要利用强联通分解，

把属于同一个强联通块的位置置于同一个字母，

然后根据前后关系建图连边

•代码

 #include<bits/stdc++.h>

 using namespace std;

 #define mem(a,b) memset(a,b,sizeof a)

 const int maxn=2e5+;

 int n,m;

 int a[maxn];

 struct Edge

 {

     int to,next;

 }G[maxn*];

 int head[maxn],cnt;

 void addEdge(int u,int v)

 {

     G[++cnt].to=v;

     G[cnt].next=head[u];

     head[u]=cnt;

 }

 int col[maxn];

 struct SCC///强联通分量分解

 {

     bool vis[maxn];

     vector<int> vs;

     void DFS(int u)

     {

         vis[u]=true;

         for(int i=head[u];i;i=G[i].next)

         {

             int v=G[i].to;

             if(!(i&)||vis[v])

                 continue;

             DFS(v);

         }

         vs.push_back(u);

     }

     void REDFS(int u,int k)

     {

         vis[u]=true;

         col[u]=k;

         for(int i=head[u];i;i=G[i].next)

         {

             int v=G[i].to;

             if((i&)||vis[v])

                 continue;

             REDFS(v,k);

         }

     }

     int scc()

     {

         vs.clear();

         mem(vis,false);

         for(int i=;i<=n;i++)

             if(!vis[i])

                 DFS(i);

         mem(vis,false);

         int k=;

         for(int i=vs.size()-;i>=;i--)

             if(!vis[vs[i]])

                 REDFS(vs[i],++k);

         return k;

     }

 }_scc;

 Edge newG[maxn*];

 int head2[maxn];

 void addnew(int u,int v)

 {

     newG[++cnt].to=v;

     newG[cnt].next=head2[u];

     head2[u]=cnt;

 }

 int Indu[maxn];

 char ch[maxn];

 queue<int >q;

 void topsort(int k)///拓扑排序

 {

     while(!q.empty())

         q.pop();

     for(int i=;i<=k;i++)

         if(!Indu[i])

             q.push(i);

     int now=;

     while(!q.empty())

     {

         int u=q.front();

         ch[u]='a'+now;

         ///>=m个不同字母,那就正好m个，后面的都置为同一个

         if(now<m-)

             now++;

         q.pop();

         for(int i=head2[u];i;i=newG[i].next)

         {

             int v=newG[i].to;

             Indu[v]--;

             if(!Indu[v])

                 q.push(v);

         }

     }

 }

 int main()

 {

     cin>>n>>m;

     for(int i=;i<=;i++)

     {

         for(int j=;j<=n;j++)

             cin>>a[j];

         for(int j=;j<=n-;j++)

         {

             addEdge(a[j],a[j+]);

             addEdge(a[j+],a[j]);

         }

     }

     int k=_scc.scc();

     if(k<m)

         puts("NO");

     else

     {

         puts("YES");

         cnt=;

         ///缩点，把每一个联通快看做一个点

         ///利用点col[i]之间的关系建图,跑拓扑序

         for(int u=;u<=n;u++)

         {

             for(int i=head[u];i;i=G[i].next)

             {

                 int v=G[i].to;

                 if(!(i&)||col[u]==col[v])

                     continue;

                 addnew(col[u],col[v]);

                 Indu[col[v]]++;

             }

         }

         topsort(k);

         for(int i=;i<=n;i++)

             cout<<ch[col[i]];

     }

 }