梁山好汉排座次-拓扑排序.cpp

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

int main()
{
    int n,r[200];//r表示每个点的入度
    string name,s[200];
    bool a[200][200],vis[200];//a邻接矩阵，vis在排序时纪录这个点是否已经确定顺序
    while (cin >> n&&n) {
        map<string, int> map;
        int i,j,k,num=0,m;
        memset(a, 0, sizeof(a));
        memset(r, 0, sizeof(r));
        memset(vis, 0, sizeof(vis));
        for (k=1; k<=n; k++) {
            cin >> name;
            i=map[name]==0 ? s[++num]=name,map[name]=num:map[name];
            cin >> name;
            j=map[name]==0 ? s[++num]=name,map[name]=num:map[name];
            //以上只是利用map确定名字代表的编号，即i和j的值
            a[i][j]=1;
            r[j]++;
        }//以上是根据关系构图
        m=num;
        while (m--) {//每次确定一个名次
            for (i=1; i<=num&&(vis[i]||r[i]); i++);//找到入度为0且还没有确定名次的点
            if (m)
                cout << s[i] << ' ';
            else cout << s[i] << '\n';
            vis[i]=1;//将该店标记为已经访问
            for (j=1; j<=num; j++)
                if (a[i][j]) {
                    a[i][j]=0;//将与之连接的边删除
                    r[j]--;
                }
        }
    }
    return 0;
}
/*
 Problem description
 中国封建社会是一个等级森严的社会，等级观念在人们心目中根深蒂固，在农民起义队伍中也摆脱不了等级观念的影响。特别是在革命成功之后，权利再分配更是起义领袖们棘手的问题，他们往往因权利分配不当致使艰苦奋斗夺得的江山一朝失落。
 梁山好汉也是生活在这个等级森严的社会里，等级观念在他们头脑中也必然有所反映。晁盖、吴用上梁山之初，在谈及林冲座次时，吴用不是认为“理合王伦让这第一头领坐，此合天下之公认”，对梁山王伦座次排定不当的不满吗？而林冲自己不也表示过，王伦“是个落第腐儒，胸中又没文学，怎做得山寨之主”的愤慨及自己“因犯下大罪”，投奔他处无门，“不得已而坐了第四位”的抱怨吗？这些出身、职业各异，性格、才智有别的好汉们，在晁盖、宋江入主梁山后，多次排座次，虽座次有先后之别、尊卑之异，但居然没有一人对此有异议，这的确是少有之事，也足以说明梁山排座次是大有学问的。
 
 梁山排法是分贵贱、问亲疏的，谁在前，谁在后，大致都有线索可寻，这些安排正体现了梁山领导核心的思想和意志。
 你的任务就是根据已有的排名条件，给梁上的英雄好汉派一个座次。
 
 
 Input
 有多组测试数据。
 每组测试数据的第一行，是一个正整数n。如果n=0表示输入结束并且不需要处理。
 以下有n行，每行包括两个不同好汉的姓名，表示这两个好汉的先后关系，两个姓名之间用一个空格隔开。
 好汉的总数不超过108，每个好汉的姓名长度不超过3个汉字也就是6个字符，好汉的姓名中间没有空格、字母、数字，只由汉字组成。
 你可以假设根据给出的先后关系，可以得到唯一确定的排名，而且在同一组测试数据中间，不会出现矛盾的先后关系。比如以下的关系就是矛盾的：
 宋江 卢俊义
 卢俊义 阮小二
 阮小二 宋江
 
 
 Output
 对于每组测试数据，输出一行，给出梁山好汉的座次表，每个姓名之间用一个空格隔开，但每行结束的地方不要出现空格。
 在输入的先后关系中没有出现的人名不要出现在你的座次表中，但在输入的先后关系中出现过的人名一定要出现在你的座次表中。
 
 
 Sample Input
 1
 宋江 卢俊义
 3
 卢俊义 宋江 
 卢俊义 阮小二 
 宋江 阮小二
 0	
 Sample Output
 宋江 卢俊义
 卢俊义 宋江 阮小二
 Judge Tips
 梁山108条好汉的姓名如下：
 "宋江","卢俊义","吴用","公孙胜","关胜","林冲","秦明","呼延灼","花荣","柴进","李应","朱仝","鲁智深","武松","董平","张清","杨志","徐宁","索超","戴宗","刘唐","李逵","史进","穆弘","雷横","李俊","阮小二","张横","阮小五","张顺","阮小七","杨雄","石秀","解珍","解宝","燕青","朱武","黄信","孙立","宣赞","郝思文","韩滔","彭?^","单廷贵","魏定国","萧让","裴宣","欧鹏","邓飞","燕顺","杨林","凌振","蒋敬","吕方","郭盛","安道全","皇甫端","王英","扈三娘","鲍旭","樊瑞","孔明","孔亮","项充","李衮","金大坚","马麟","童威","童猛","孟康","侯健","陈达","杨春","郑天寿","陶宗旺","宋清","乐和","龚旺","丁得孙","穆春","曹正","宋万","杜迁","薛永","施恩","李忠","周通","汤隆","杜兴","邹渊","邹润","朱贵","朱富","蔡福","蔡庆","李立","李云","焦挺","石勇","孙新","顾大嫂","张青","孙二娘","王定六","郁保四","白胜","时迁","段景住" 
*/