gym /102501 G Swapping Places 拓扑排序+优先队列 思维优化

只考虑朋友关系之间相互移动太难做了。

正难则反，考虑不是朋友关系的一对位置，他们的相对位置一定不变。

这样就能构建出一个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;
}