点这里
【#|HDU3342 Legal or Not——拓扑排序（裸题）】题意： n个人和m对人机关系，每对人机关系x、y表示x是y的师傅。人机关系具有传递性，即我的师傅的师傅也是我的师傅，我的徒弟的徒弟也是我的徒弟。要求找出人际关系中是否含有不合法的，即如果出现某个人既是我的师傅，也是我的徒弟，则关系不合法，输出NO，全都合法输出YES。
题解： 刚看题意觉得新鲜，其实就是拓扑排序的裸题，按照拓扑排序的模板走完，如果还要人的入度不为0，说明内部构成了循环，而构成循环的原因就是出现了不合法的关系。
#include
using namespace std;
const int N = 110;
int n, m, a, b;
int deg[N], G[N][N];
void BFS(){
queue q;
for(int i = 0;
i < n;
i++) if(!deg[i]) q.push(i);
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = 0;
i < n;
i++){
if(G[u][i]){
deg[i]--;
if(!deg[i]) q.push(i);
}
}
}
for(int i = 0;
i < n;
i++) if(deg[i]) {printf("NO\n");
return;
}
printf("YES\n");
}
int main(){
while(~scanf("%d%d", &n, &m) && n){
memset(deg, 0, sizeof deg);
memset(G, 0, sizeof G);
while(m--){
scanf("%d%d", &a, &b);
if(G[a][b]) continue;
G[a][b] = 1;
deg[b]++;
}
BFS();
}
}
推荐阅读
- 数据结构和算法|LeetCode 的正确使用方式
- #|7.分布式事务管理
- #|算法设计与分析（Java实现）——贪心算法（集合覆盖案例）
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- #|阿尔法点亮LED灯(一）汇编语言
- #|Multimedia
- #|ARM裸机开发（汇编LED灯实验（I.MX6UL芯片））
- 基础课|使用深度优先搜索（DFS）、广度优先搜索（BFS）、A* 搜索算法求解 (n^2 -1) 数码难题，耗时与内存占用（时空复杂度）对比（附（(n^2 - 1) 数码问题控
- #|学习笔记 | Ch05 Pandas数据清洗 —— 缺失值、重复值、异常值
- win10|搏一搏 单车变摩托，是时候捣鼓一下家中的小米电视机啦。