题目大意:
给你一个关系图,判断是否合法,
每个人都有师父和徒弟,可以有很多个;
但是你的师父不能是你徒弟的徒弟,或者说你的徒弟不能是你师父的师父,这是不合法的情况。
简单理解就是:判断有向图中是否存在3元环;
此题至少有三种做法,此处跟新拓扑排序的做法:
1. 拓扑排序:
1. 统计每个点的入度;
2. 将入度为0的点加入队列;
3. 出去队首元素,将此元素所连接的点入度减一,若此后入度为0则加入队列;
4. 判断队列循环次数,若等于n则不存在3元环,则此关系图合法;
题目链接:
点击打开链接
#include
#include
#include
#include
#include
#include
#include
#include
View Code