G. Swapping Places

题目链接：https://codeforces.ml/gym/294361/problem/G

题意：给你一些动物，以及一些动物的关系，如果两种动物是朋友，那他们就可以交换位置，最后再给你一个队列，你可以让一些朋友交换位置，问队列的最小字典序是哪个。

思路：先给动物排个序，然后可以用序号来代替动物名字，再根据他们是否是朋友来进行标记和建边，最后再跑一遍拓扑排序即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<string,int > mp;
int book[205][205];
string a[205];
int b[200005],sum[205],c[200005],num[205],p[200005];
vector<int> ve[205];
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1; i<=n; i++)
    {
        mp[a[i]]=i;
        book[i][i]=1;
    }
    for(int i=1; i<=m; i++)
    {
        string x,y;
        cin>>x>>y;
        book[mp[x]][mp[y]]=book[mp[y]][mp[x]]=1;
    }
    for(int i=1; i<=k; i++)
    {
        string x;
        cin>>x;
        b[i]=mp[x];
    }
    for(int i=1; i<=k; i++)
    {
        int cnt=0;
        for(int j=1; j<=n; j++)
        {
            if(!book[b[i]][j])
            {
                cnt+=sum[j];
            }
        }
        ve[b[i]].push_back(cnt);
        sum[b[i]]++;
    }
    for(int i=1; i<=k; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(c[j]<ve[j].size())
            {
                if(ve[j][c[j]]==num[j])
                {
                    c[j]++;
                    p[i]=j;
                    for(int k=1; k<=n; k++)
                    {
                        if(!book[k][j])
                        {
                            num[k]++;
                        }
                    }
                    break;
                }
            }
        }
    }
    for(int i=1; i<=k; i++)
        cout<<a[p[i]]<<' ';
    cout<<endl;
}