[蓝桥杯][算法提高VIP]卡勒沃夫之弱水路三千(提高型)

[蓝桥杯][算法提高VIP]卡勒沃夫之弱水路三千(提高型)
输入
第一行为一个不超过5的整数T，表示数据的组数。之后每组数据的一行为一个不超过100的整数n。之后n行每行有两个用单个空格隔开的字符串（每个字符串只有英文大小写字母，长度不超过10），为两位mm的名字。每行第一个mm先于第二个mm成为某人的女友。
在这里我们假装诅咒某人不会同时被两个或两个以上mm泡，某个mm抛弃了某人后不会再吃回头草，同时卡勒沃夫深邃的洞察力使得他收集到了充足的信息以确定某人女友的先后顺序。
在小数据组中出现的人物不超过13个

题解：

这种根据比较关系来判断先后顺序，用拓扑排序

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e2+9;
vector<int>edge[maxn];
map<int,string>tran;
map<string,int>change;
int in[maxn];
vector<int>w;
queue<int>q;
void toop(int x)
{
    q.push(x);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        w.push_back(u);
        for(int i=0;i<edge[u].size();i++)
        {
            int v=edge[u][i];
            in[v]--;
            if(in[v]==0)q.push(v);
        }
    }
    for(int i=0;i<w.size();i++)
    {
        if(i==w.size()-1)cout<<tran[w[i]];
        else cout<<tran[w[i]]<<" ";
    } 
    cout<<endl;
    return ;
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int sum=0;
        memset(in,0,sizeof(in));
        tran.clear();
        change.clear();
        for(int i=0;i<maxn;i++)edge[i].clear();
        for(int i=0;i<w.size();i++)w.clear();
        for(int i=1;i<=n;i++)
        {
            string a,b;
            cin>>a>>b;
            if(change[a]==0)
            {
                change[a]=++sum;
                tran[sum]=a;
            }
            if(change[b]==0)
            {
            change[b]=++sum;
            tran[sum]=b;                
            }

            edge[change[a]].push_back(change[b]);
            in[change[b]]++;
        }
        int i;
        for(i=1;i<=sum;i++)if(in[i]==0)break;
        toop(i);
    }
}