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

解题思路:拓扑排序

    当一个点的入度为0时候，那么此刻她是当前女友。

注意事项:因为是多组测试数据，因此需要处理好初始化的工作，否则容易出现部分正确的情况。

参考代码:

#include<iostream>
#include<algorithm>
#include<map>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
using namespace std;

int cnt,InNum[110],res[110],vis[110];
vector<int>Next[110];

map<string,int>mp; 
map<int,string>names;

int num(string name)
{
	if(mp.find(name)==mp.end())
	{
		mp[name]=++cnt;
		names[cnt]=name;
	}
	return mp[name];
}
/*
void dfs(int pre,int dep,int*res,int &ok)
{
	if(ok==true) return ;
	for(set<int>::iterator it=next[pre].begin();it!=next[pre].end();it++)//寻找 
	{
		int u = *it;
		if(!vis[u])
		{
			int flag = true;
			for(int k=1;k<=dep-1;k++)
			{
				int p=res[k];
				if(prex[p].find(u)!=prex[p].end())
				{
					flag=false;
					break;
				}
			}
			if(flag==false) continue;
			vis[u]=true;
			res[dep]=u;
			if(dep==cnt)
			{
				ok=true;
				for(int i=1;i<=cnt;i++)
				{
					cout<<names[i];
					if(i!=cnt) cout<<" ";
 				}
			}
			else
			{
				dfs(u,dep+1,res,ok);
			}
			vis[u]=false;
		}
	}
}
*/
int main(void)
{
	//freopen("D:\\input1.txt","r",stdin);
	int T,n;
	cin>>T;
	while(T--)
	{
		//初始化 
		cnt=0;
		mp.clear();
		names.clear();
		for(int i=0;i<110;i++) Next[i].clear(); 
		memset(vis,0,sizeof(vis));
		memset(InNum,0,sizeof(InNum));
		
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			string name1,name2;
			cin>>name1>>name2;
			int num1=num(name1);
			int num2=num(name2);
			Next[num1].push_back(num2);
			InNum[num2]++;//入度加一 
		}
		queue<int>Q;
		for(int i=1;i<=cnt;i++) if(InNum[i]==0) 
		{
			vis[i]=true;
			Q.push(i);
		}
		int count=0;
		while(!Q.empty())
		{
			count++;
			int t = Q.front(); Q.pop(); 
			res[count]=t;
			for(int i=0;i<Next[t].size();i++)
			{
				int p = Next[t][i];
				InNum[p]--;
			}
			for(int i=1;i<=cnt;i++) if(InNum[i]==0 && vis[i]==false)
			{
				vis[i]=true;
				Q.push(i);
			}
		}
		for(int i=1;i<=cnt;i++) 
		{
			cout<<names[res[i]];
			if(i!=cnt)	cout<<" ";
		}
		if(T) cout<<endl; 
	}
	return 0;
}