(错误%9)蓝桥杯算法提高VIP-士兵排队问题 （C++代码）

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
using namespace std;
//int a[100],b[100];
//set<int>Next[30];//前提是一个点到另一个点的之间有一条，但是这题会出现重复的现象
vector<int>Next[300]; 
//vector<int>peop;//枚举People需要字典序排列，vector改成set
set<int> peop;
int In[300],have[300],vis[300],res[300],num;//num record the numbers of people 
/*
void qsort(int L,int R)
{
	int i=L,j=R,mid;
	while(i<=j)
	{
		int mid=a[(i+j)/2];
		while(a[i]<mid) i++;
		while(a[j]>mid) j--;
		if(i<=j)
		{
			swap(a[i],a[j]);
			swap(b[i],b[j]);
			i++,j--;
		} 
	}
	if(L<j) qsort(L,j);
	if(i<R) qsort(i,R);
}
*/
int main(void)
{
	//freopen("D:\\input10.txt","r",stdin);
	char res[110];
	int count=0;
	while(cin.getline(res,100))
	{
		//cout<<res<<endl;
		
		int p1=res[0]-'A';
		int p2=res[2]-'A';
		count++;
		//a[count]=p1;
		//b[count]=p2;
		//cout<<"p1="<<p1<<" p2="<<p2<<endl;
		if(have[p1]==false)
		{
			have[p1]=true;
			peop.insert(p1); 
			num++;
		}
		if(have[p2]==false)
		{
			have[p2]=true;
			peop.insert(p2);
			num++;
		}
		//Next[p1].insert(p2);
		Next[p1].push_back(p2);
		In[p2]++;
	}
	/*
	qsort(1,count);
	for(int i=1;i<=count;i++) 
	{
		printf("%c %c\n",a[i]+'A',b[i]+'A'); 
	} 
	for(int i=0;i<26;i++) cout<<have[i];
	cout<<endl; 
	*/
	int cnt=0,ans[100];//record the people who mean 
	queue<int>q;
	for(set<int>::iterator it=peop.begin();it!=peop.end();it++)
	{
		int p = *it;
		if(In[p]==0)
		{
			vis[p]=true;
			q.push(p);
		}
	}
	//cout<<"num="<<num<<endl;
	while(!q.empty())
	{
		int p = q.front(); q.pop();
		//cout << (char)('A'+p)<<endl;
		ans[++cnt]=p;
		if(cnt==num)
		{
			for(int i=1;i<=num;i++) cout<<(char)('A'+ans[i]);
		}
		for(int i=0;i<Next[p].size();i++)
		{
			//后继节点入度减一 
			int u = Next[p][i];
			In[u]--;
		}
		for(set<int>::iterator it=peop.begin();it!=peop.end();it++)
		{
			int x = *it;
			//cout<<In[x]<<" ";
			if(In[x]==0 && vis[x]==false)
			{
				vis[x]=true;
				q.push(x);
			}
		}
		//cout<<endl;
	}
	if(cnt!=num) cout<<"No Answer!";
	return 0;
}