拓扑排序--九度1450.产生冠军

2017年3月11日 5点热度 0条评论 来源: 3stone_

【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;
}
    原文作者:3stone_
    原文地址: https://blog.csdn.net/qq_26398495/article/details/61317337
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。