【2017/3/10】 注意：要有冠军，初始时入度为0的点只能有一个
/******************3stone***************************** FileName: 九度1450.产生冠军 Author：3stone Time：2017/3/10 *****************3stone*****************************/ #include<cstdio> #include<queue> #include<vector> #include<iostream> #include<map> using namespace std; int main(){ int n; string a, b; while(scanf("%d", &n) != EOF){ if(0 == n) break; map<string, int> inCount; //以名字为键值 map<string, vector<string> > edge; //链表，名字做键值 for(int i = 0; i < n; i++){ cin >> a >> b; if(inCount.find(b) == inCount.end()) inCount[b] = 1; //入度+1 else inCount[b]++; if(inCount.find(a) == inCount.end()) inCount[a] = 0; //此处没有清空呀 edge[a].push_back(b); //a指向b } int total_num = inCount.size(); while(que.empty() == false) que.pop(); map<string, int>::iterator it; for(it = inCount.begin(); it != inCount.end(); it++){//入度为0入栈 if(0 == it->second) que.push(it->first); } int start = que.size(); //注意初始入度为0的点若有多个 //则无法确定谁是冠军 int cnt = 0; while(que.empty() == false){ //出队列 string nowp = que.front(); que.pop(); // if(0 == cnt) printf("%d", nowp); // else printf(" %d", nowp); cnt++; //记录入度为0的点数 vector<string>::iterator it1; for(it1 = edge[nowp].begin(); it1 != edge[nowp].end(); it1++){//入度为0入栈 inCount[*it1]--; if(0 == inCount[*it1]) que.push(*it1); } }//while--queue if(cnt == total_num && 1 == start) printf("Yes\n"); else printf("No\n"); }//while return 0; }