首页 > 代码库 > ZZUOJ - 1199 - 大小关系 （拓扑排序！）
ZZUOJ - 1199 - 大小关系 （拓扑排序！）
1199: 大小关系
Time Limit: 2 Sec Memory Limit: 128 MBSubmit: 126 Solved: 27
[Submit][Status][Web Board]
Description
当我们知道一组大小关系之后，可判断所有关系是否都能成立，即关系间没有矛盾。
例如：A<B, A<C, B<C 通过这组关系我们可以得到A<B<C ，所有关系都成立，没有矛盾。
若 A<B, B<C, C<A 通过前两个关系我们得到 A<B<C ，这个关系与C<A矛盾，所有关系不能同时成立。
现在我们知道m个关系,请判断这m个关系是否能成立，成立输出“YES”，否则输出“NO”。
Input
多组数据，每组数据如下：
第一行有一个数字m。 m代表m组关系(1<=m<=400)，接下来m行每行有一个关系，用两个不同的字母和一个符号表示。（输入保证字母在‘A’-‘Z’之间，关系符号只有 > , <）
Output
对于每组数据输出“YES”或“NO”.
Sample Input
3
A<B
A<C
B<C
3
A<B
B<C
C<ASample Output
YES
NOHINT
Source
郑州大学第七届ACM大学生程序设计竞赛
最近数据结构在讲图论的拓扑排序，正好刷个题来耍耍，简单拓扑排序。。
AC代码（有点挫(⊙o⊙)…，第一次写）：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <stack>
using namespace std;
int indegree[26]; //记录入度
int visit[26]; //判断是否读入过
typedef struct node
{
char data;
struct node *p;
}list;
list zu[26];
void init() //初始化
{
for(int i=0; i<26; i++)
{
zu[i].p = NULL;
zu[i].data = http://www.mamicode.com/(char)(i+65);>
ZZUOJ - 1199 - 大小关系 （拓扑排序！）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。