HDOJ 3342 Legal or Not 【拓扑排序】

本文主要是介绍HDOJ 3342 Legal or Not 【拓扑排序】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：判断是否成环。

策略：如题。

这道题就是简单的拓扑排序题，但是要注意一点要去重复的数据。我用了两种结构体：链式前向星和邻接矩阵。

代码1：（用链式前向星）（不用增加去重）

#include<stdio.h>
#include<string.h>
#include<queue>
#define INF 0x3f3f3f3f
#define MAXN 105
struct EdgeNode{int to;int next;
}edges[MAXN];
int head[MAXN], n, in[MAXN], queue[MAXN];
int toposort()
{int i, iq = 0, j;for(i = 0; i < n; i ++){if(!in[i]){queue[iq++] = i;}}for(i = 0; i < iq; i ++){int temp = queue[i];for(j = head[temp]; j != -1; j = edges[j].next){if(!--in[edges[j].to]){queue[iq++] = edges[j].to;}}}return iq == n;
}
int main()
{int m, a, b, i;while(scanf("%d%d", &n, &m), n||m){memset(head, -1, sizeof(head));memset(in, 0, sizeof(in));for(i = 0; i < m; i ++){scanf("%d%d", &a, &b);edges[i].to = b;edges[i].next = head[a];head[a] = i;++in[b];}printf("%s\n", toposort()?"YES":"NO");}
}

代码2：（用邻接矩阵） 事实证明链式前向星更快

#include<stdio.h>
#include<string.h>
#include<queue>
#define INF 0x3f3f3f3f
#define MAXN 105
int map[105][105];
int queue[MAXN], in[MAXN];
int n;
int toposort()
{int i, j;int iq = 0;for(i = 0; i < n; i ++){if(!in[i]){queue[iq++] = i;}}for(i = 0; i < iq; i ++){int temp = queue[i];for(j = 0; j < n; j ++){if(map[temp][j]){--in[j];if(!in[j]){queue[iq++] = j;}}}}return iq == n;
}
int main()
{int m, i, j, a, b;while(scanf("%d%d", &n, &m), n||m){memset(map, 0, sizeof(map));memset(in, 0, sizeof(in));for(i = 0; i < m; i ++){scanf("%d%d", &a, &b);if(!map[a][b]){ //去重map[a][b] = 1;in[b]++;}}printf("%s\n", toposort()?"YES":"NO");}return 0;
} 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3342

这篇关于HDOJ 3342 Legal or Not 【拓扑排序】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---