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

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

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

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

•代码

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define mem(a,b) memset(a,b,sizeof a)
  4 const int maxn=2e5+5;
  5 int n,m;
  6 int a[maxn];
  7 struct Edge
  8 {
  9     int to,next;
 10 }G[maxn*10];
 11 int head[maxn],cnt;
 12 void addEdge(int u,int v)
 13 {
 14     G[++cnt].to=v;
 15     G[cnt].next=head[u];
 16     head[u]=cnt;
 17 }
 18 
 19 int col[maxn];
 20 struct SCC///强联通分量分解
 21 {
 22     bool vis[maxn];
 23     vector<int> vs;
 24 
 25     void DFS(int u)
 26     {
 27         vis[u]=true;
 28         for(int i=head[u];i;i=G[i].next)
 29         {
 30             int v=G[i].to;
 31             if(!(i&1)||vis[v])
 32                 continue;
 33             DFS(v);
 34         }
 35         vs.push_back(u);
 36     }
 37 
 38     void REDFS(int u,int k)
 39     {
 40         vis[u]=true;
 41         col[u]=k;
 42         for(int i=head[u];i;i=G[i].next)
 43         {
 44             int v=G[i].to;
 45             if((i&1)||vis[v])
 46                 continue;
 47             REDFS(v,k);
 48         }
 49     }
 50 
 51     int scc()
 52     {
 53         vs.clear();
 54         mem(vis,false);
 55         for(int i=1;i<=n;i++)
 56             if(!vis[i])
 57                 DFS(i);
 58 
 59         mem(vis,false);
 60         int k=0;
 61         for(int i=vs.size()-1;i>=0;i--)
 62             if(!vis[vs[i]])
 63                 REDFS(vs[i],++k);
 64 
 65         return k;
 66     }
 67 }_scc;
 68 
 69 
 70 Edge newG[maxn*10];
 71 int head2[maxn];
 72 void addnew(int u,int v)
 73 {
 74     newG[++cnt].to=v;
 75     newG[cnt].next=head2[u];
 76     head2[u]=cnt;
 77 }
 78 int Indu[maxn];
 79 char ch[maxn];
 80 queue<int >q;
 81 void topsort(int k)///拓扑排序
 82 {
 83     while(!q.empty())
 84         q.pop();
 85     for(int i=1;i<=k;i++)
 86         if(!Indu[i])
 87             q.push(i);
 88 
 89     int now=0;
 90     while(!q.empty())
 91     {
 92         int u=q.front();
 93         ch[u]='a'+now;
 94         ///>=m个不同字母,那就正好m个，后面的都置为同一个
 95         if(now<m-1)
 96             now++;
 97         q.pop();
 98         for(int i=head2[u];i;i=newG[i].next)
 99         {
100             int v=newG[i].to;
101             Indu[v]--;
102             if(!Indu[v])
103                 q.push(v);
104         }
105     }
106 }
107 int main()
108 {
109     cin>>n>>m;
110     for(int i=1;i<=2;i++)
111     {
112         for(int j=1;j<=n;j++)
113             cin>>a[j];
114         for(int j=1;j<=n-1;j++)
115         {
116             addEdge(a[j],a[j+1]);
117             addEdge(a[j+1],a[j]);
118         }
119     }
120     int k=_scc.scc();
121     if(k<m)
122         puts("NO");
123     else
124     {
125         puts("YES");
126         cnt=0;
127         
128         ///缩点，把每一个联通快看做一个点
129         ///利用点col[i]之间的关系建图,跑拓扑序
130         for(int u=1;u<=n;u++)
131         {
132             for(int i=head[u];i;i=G[i].next)
133             {
134                 int v=G[i].to;
135                 if(!(i&1)||col[u]==col[v])
136                     continue;
137                 addnew(col[u],col[v]);
138                 Indu[col[v]]++;
139             }
140         }
141         topsort(k);
142 
143         for(int i=1;i<=n;i++)
144             cout<<ch[col[i]];
145     }
146 }

View Code