HDOj 2094 產生冠軍（拓撲排序）

只需統計無沒有前驅結點的結點個數即可，如果是環，是0個，如果有不確定的，那麼肯定>1

利用STL裡的map，string，set容器可以簡潔地實現

代碼如下：

[cpp]
#include<iostream>  
#include<map>  
#include<set>  
#include<string>  
using namespace std; 
 
map<string,string>G; 
set<string>Set; 
set<string>::iterator p; 
 
int main(){ 
    int n,i; 
    string a; 
    string b; 
    //freopen("1.txt","r",stdin);  
    while(cin>>n,n){ 
        G.clear(); 
        Set.clear(); 
        for(i=1;i<=n;i++){ 
            cin>>a>>b; 
            Set.insert(a); 
            Set.insert(b); 
            G[b]=a; 
        } 
        i=0; 
        for(p=Set.begin();p!=Set.end();p++){ 
            if(G[*p].length()==0) 
                i++; 
        } 
        if(i==1) 
            cout<<"Yes"<<endl; 
        else 
            cout<<"No"<<endl; 
    } 
    return 0; 
} 

#include<iostream>
#include<map>
#include<set>
#include<string>
using namespace std;

map<string,string>G;
set<string>Set;
set<string>::iterator p;

int main(){
 int n,i;
 string a;
 string b;
 //freopen("1.txt","r",stdin);
 while(cin>>n,n){
  G.clear();
  Set.clear();
  for(i=1;i<=n;i++){
   cin>>a>>b;
   Set.insert(a);
   Set.insert(b);
   G[b]=a;
  }
  i=0;
  for(p=Set.begin();p!=Set.end();p++){
   if(G[*p].length()==0)
    i++;
  }
  if(i==1)
   cout<<"Yes"<<endl;
  else
   cout<<"No"<<endl;
 }
 return 0;
}