拓扑排序 soj1075-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

拓扑排序 soj1075

简介:

     1075: BlueEyes and Apples (II)

The Problem

袁源除了喜欢吃苹果外,他在有空的时候还喜欢把苹果按重量由大到小排成一列.当然,这是为了方便以后从最大的开始吃,这样他就能永远都吃到最大的!但是他只有一部没有砝码的天平,于是他每次只能比较两个苹果的重量。现在就要请你帮忙,如果每次只给出两个苹果的重量关系,怎样才能把这些苹果都排列好呢?

输入

本题包括多组测试数据.每组测试数据的第一行为一个整数n(1<=n<=20),代表一共的比较次数,接下来的n行,每行包括两个大写字母x和y,代表x的重量大于y.当n=0时代表输入结束,这组数据不包括在需要计算的数据中.

输出

对每一组输入数据,输出一个排列方案。对于每一组输入数据,有且只有唯一的一种排列方案.

样例输入

3
A B
B C
C D
4
A B
A C
D A
C B
0

样例输出

A B C D
D A C B
题意:给出一组输入,将输入按照从小到大的顺序输出。
看第一组数据:
A B 即A-->B;B C 即 B-->C,即A-->B-->C;C D 即C-->D,A-->B-->C-->D;
看第二组数据:                  
A B 即A-->B;A C 即A-->C,即
;C B,即;D A,即
从上面分析可以看出,其实输出序列就是该有向图的拓扑排序序列。
复制代码
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#define MAX 26
usingnamespace std;

int map[MAX][MAX];
int indegree[MAX];
int p[MAX];

void toposort(char s[MAX]) //进行拓扑排序 
{
    int i,j,k,t;
    t=0;
    for(i=0;i<MAX;i++) //遍历 
    {
        for(j=0;j<MAX;j++) //寻找入度为0的点,并且该点被标记为1,即该点被使用 
        {
            
            if(indegree[j]==0&&p[j]==1)
            {
                indegree[j]--; //入度自减 
                s[t++]=j+65; //把该点表示的字符赋给s[t] 
                for(k=0;k<MAX;k++) //删除与j有关联的边,并使入度减1 
                {
                    if(map[j][k]==1)
                    {
                        indegree[k]--;
                    }
                }
                break;
            }
        }
    }
    s[t]='\0';
}

int main(void)
{
    int t;
    while(scanf("%d",&t)==1&&t!=0)
    {
        int i;
        char x,y;
        char s[MAX];
        memset(map,0,sizeof(map));
        memset(p,0,sizeof(p));
        memset(indegree,0,sizeof(indegree));
        for(i=0;i<t;i++)
        {
            getchar();
            scanf("%c %c",&x,&y);
            if(!map[x-65][y-65])
            {
                p[x-65]=1;
                p[y-65]=1;
                map[x-65][y-65]=1; //关联边赋值为1 
                indegree[y-65]++; //入度加1 
            }
        }
        toposort(s);
        for(i=0;i<strlen(s)-1;i++)
        {
            printf("%c ",s[i]);
        }
        printf("%c\n",s[i]);
    }
    return0;
}

如需转载自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: