蓝桥杯算法提高VIP-卡勒沃夫之弱水路三千(提高型) （C++代码）拓扑排序

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<vector>
#include<map>
#include<cstring>
#include<queue>
#include<set>
using namespace std;
map<string,int> si;
map<int,string> is;
vector<int> edge[1005];
vector<string>ans;
int in[1005];
int t, n;
string a, b;
int main()
{
    int num;
    cin >> t;
    while(t--){
        cin>> n;
        //因为多组操作每次需前清空
        num = 0;
        si.clear();
        is.clear();
        ans.clear();
        memset(in, 0, sizeof(in));
        for(int i=0;i<=n;i++) edge[i].clear();
        while(n--){
            cin >> a>>b;
            //查询si中有无a女友
            if(!si.count(a))
            {
                si[a]=num; is[num]=a;
                num++;
            }
            if(!si.count(b))
            {
                si[b]=num; is[num]=b;
                num++;
            }
            edge[si[a]].push_back(si[b]);
            in[si[b]]++;
        }
        queue<int>q;
        for(int i=0;i<num;i++)
         if(in[i]==0) q.push(i);
        while(!q.empty())
        {
            int k=q.front(); q.pop();
            ans.push_back(is[k]);
            for(int i=0;i<edge[k].size();i++)
            {
                int v=edge[k][i];
                in[v]--;
                if(in[v]==0) q.push(v);
            }
        }
        for(int i=0;i<ans.size()-1;i++) cout<<ans[i]<<" ";
        cout<<ans[ans.size()-1]<<endl;
    }
    return 0;
}