图论-士兵排序

解题思路：首先理解本题考察的是**拓扑排序

有考虑到时间可能会超时，所有进行 双向 搜索

set<int>str_out[26];//记录出度 

 set<int>str_in[26];//记录入度为0的点同时保存点的边信息 

memset(station,0,sizeof(station));

 while(scanf("%s",&str)!=EOF)

 {

     str_out[str[0]-'A'].insert(str[2]-'A');        //str[0] - 'A'表示的是某一个字符 对应的  出度 指向（A--->B）

     str_in[str[2]-'A'].insert(str[0]-'A');//这个在后边用于找入度为0的点和存储边信息

     station[str[0]-'A']=1;//记录排队的人，

     station[str[2]-'A']=1; 

 }

接下来就是 进队列的了         首先是入度为零   的开始进行入队列 

queue<int>p;

     int ans[26],k=0;//记录排队顺序 

     for(int i=0;i<26;i++)

     {

         if(str_in[i].size()==0&&station[i])//两者缺一不可 

         p.push(i);//入度为0的入队 

     }

//接下来就是出队列了

while(!p.empty()) 

     {

         int j=p.front(); //开始消除 每个入度为零的

         for(set<int>::iterator it=str_out[j].begin();it!=str_out[j].end();it++)

         {

             int t=*it;

             str_in[t].erase(j);//删除t点的所有出边       消除边   ！！！

             if(str_in[t].size()==0)

             p.push(t);//将t点入队（因为他已经是入度为0的点） 

         }

         str_out[j].clear();//删除j点的所有出边 

         ans[k++]='A'+j;

         p.pop(); 

     }

直到 队列为空 则所有的 遍历完成

***************************

#include<bits/stdc++.h> 

using namespace std;

int main()

{

 int station[26];//保存在本次排队中的点 

 char str[3];

 set<int>str_out[26];//记录出度 

 set<int>str_in[26];//记录入度为0的点同时保存点的边信息 

 memset(station,0,sizeof(station));

 while(scanf("%s",&str)!=EOF)

 {

     str_out[str[0]-'A'].insert(str[2]-'A');

     str_in[str[2]-'A'].insert(str[0]-'A');//这个在后边用于找入度为0的点和存储边信息

     station[str[0]-'A']=1;//记录排队的人，用于找入度为0的点

     station[str[2]-'A']=1; 

 }

     queue<int>p;

     int ans[26],k=0;//记录排队顺序 

     for(int i=0;i<26;i++)

     {

         if(str_in[i].size()==0&&station[i])//两者缺一不可 

         p.push(i);//入度为0的入队 

     }

     while(!p.empty()) 

     {

         int j=p.front();

         for(set<int>::iterator it=str_out[j].begin();it!=str_out[j].end();it++)

         {

             int t=*it;

             str_in[t].erase(j);//删除t点的所有出边

             if(str_in[t].size()==0)

             p.push(t);//将t点入队（因为他已经是入度为0的点） 

         }

         str_out[j].clear();//删除j点的所有出边 

         ans[k++]='A'+j;

         p.pop(); 

     }

     int i;

     for( i=0;i<26;i++)

     if(str_in[i].size()>0)//有环存在

     break;

     if(i==26)

     {

         for(int j=0;j<k;j++)

         printf("%c",ans[j]);

     }

     else

     printf("No  Answer!\n");

 return 0;

}