只考虑朋友关系之间相互移动太难做了。
正难则反，考虑不是朋友关系的一对位置，他们的相对位置一定不变。
这样就能构建出一个DAG，(每个点只连其前面一个和后面一个点，最多2N条边)
然后拓扑排序下 + 优先队列放置最小字典序的串即可！
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define re register #define ls (o<<1) #define rs (o<<1|1) //#define m (l+r)/2 #define pb push_back const double PI= acos(-1.0); const int M = 1e5+7; const int N =1e4+7; /* int head[M],cnt=1; void init(int n){cnt=1;for(int i=0;i<=n;i++)head[i]=0;} struct EDGE{int to,nxt,w;}ee[M*2]; void add(int x,int y,int w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;} */ string s; map<string,int>mp,mm; map<int,string>to; int a[210][210]; int p[M],du[M],nxt[M][202]; int vs[M];//某个位置的字符是否固定 vector<int>pr,G[M]; struct node{ int id,w; bool operator < (const node & r)const{ if(w==r.w) return id>r.id; return w>r.w; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); int S,L,n,sz=0; cin>>S>>L>>n; for(int i=1;i<=S;i++){ cin>>s; mm[s]=i; } for(auto x:mm) mp[x.first]=++sz,to[sz]=x.first; for(int i=1;i<=L;i++){ string u,v; cin>>u>>v; a[mp[u]][mp[v]]=a[mp[v]][mp[u]]=1; } // cout<<"ok0"<<endl; priority_queue<node>q; for(int i=1;i<=n;i++){ cin>>s; int w=mp[s]; p[i]=w; } for(int i=n;i>=1;i--){ for(int j=1;j<=S;j++)nxt[i][j]=nxt[i+1][j]; int w = p[i]; for(int j=1;j<=S;j++){ if(!a[w][j]){ if(nxt[i][j]!=0)du[nxt[i][j]]++,G[i].pb(nxt[i][j]); //cout<<" -=-=-=- "<<i<<" "<<j<<" "<<nxt[i][j]<<endl; } } nxt[i][p[i]]=i; } for(int i=1;i<=n;i++)if(du[i]==0)q.push(node{i,p[i]}); //cout<<" = == = "<<i<<endl;; while(!q.empty()){ node tp = q.top();q.pop(); int x=tp.id,w=tp.w; pr.pb(w); // cout<<x<<" - "<<w<<endl; for(auto y:G[x]){ du[y]--; if(du[y]==0)q.push(node{y,p[y]}); } } for(auto x:pr){ cout<<to[x]<<" "; } cout<<endl; return 0; }
