https://vjudge.net/problem/Gym-102501G

题意：

给你一个列表，L个可以交换的对（相邻的才能交换），问最后list表的字典序最小

解析：

发现不能交换的两种物品，其组成的相对位置不会改变。相同种类物品之间也不会改变。所以将这些相对位置建成边。跑一个字典序最小的拓扑排序就行。（优先队列）

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define LD long double
#define rep(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define per(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define pill pair<int, int>
#define fi first
#define se second
void test(){ cerr<<"\n";}
template<typename T,typename... Args>void test(T x,Args... args){ cerr<<"> "<<x<<" ";test(args...);}
const LL mod=1e9+7;
const int maxn=1e5+9;
const int inf=0x3f3f3f3f;
LL rd(){  LL ans=0; char last=' ',ch=getchar();
    while(!(ch>='0' && ch<='9'))last=ch,ch=getchar();
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')ans=-ans; return ans;
}
#define rd rd()



int s,l,n;
string x[209];
bool link[209][209];
int last[209];
int ID[100009];

vector<int>ed[100009];
int deg[100009];
void add(int a,int b){ 
    ed[a].push_back(b);
    deg[b]++;
}

struct node{ 
    int pos,val;
    bool operator<(const node &A)const{ 
        return val>A.val;
    }
};
priority_queue<node>Q;

int main(){ 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>s>>l>>n;

    rep(i,1,s){ 
        cin>>x[i];
    }
    sort(x+1,x+1+s);
    rep(i,1,l){ 
        string a,b;
        cin>>a>>b;
        int ida,idb;
        ida=lower_bound(x+1,x+1+s,a)-x;
        idb=lower_bound(x+1,x+1+s,b)-x;
        link[ida][idb]=link[idb][ida]=1;
    }
    rep(i,1,n){ 
        string a;
        cin>>a;

        int id=lower_bound(x+1,x+1+s,a)-x;
        ID[i]=id;
        if(last[id]){ 
            add(last[id],i);
        }
        last[id]=i;
        rep(j,1,s){ 
            if(j!=id&&link[j][id]==0&&last[j]){ 
                add(last[j],i);
            }
        }
    }

    rep(i,1,n){ 
        if(deg[i]==0){ 
            Q.push({ i,ID[i]});
        }
    }
    while(!Q.empty()){ 
        node P=Q.top();Q.pop();
        cout<<x[P.val]<<" ";
        for(int i=0;i<ed[P.pos].size();i++){ 
            int u=ed[P.pos][i];
            deg[u]--;
            if(deg[u]==0){ 
                Q.push({ u,ID[u]});
            }
        }
    }



    return 0;
}