hdu3342 Legal or Not(拓扑排序)

    xiaoxiao2021-12-10  8

    http://acm.hdu.edu.cn/showproblem.php?pid=3342

    题意:如果有A认为他是B的师傅,B认为A是他的师傅,那就说这里出现了矛盾,是不合法的。

    思路:本题利用拓扑排序判环,判环的条件就是在排序过程中,如果出现其中任何一个点的入度都不为0,那么此时有环。自己模拟下就好嘛,图论就是这么玩的= =。还有这题边的输入过程中要判断重边。deg[N]代表有多少人认为他是徒弟。

    #include <stdio.h> #include <algorithm> #include <stdlib.h> #include <string.h> #include <iostream> using namespace std; typedef long long LL; const int N = 1000; const int INF = 0x3f3f3f3f; int deg[N], n, cnt; bool G[N][N]; int toposort() { for(int i = 0; i < n; i++) { int k = n; for(int j = 0; j < n; j++) { if(deg[j] == 0) { k = j; deg[j]--; break; } } if(k == n) return 0; for(int j = 0; j < n; j++) { if(G[k][j] == true) { G[k][j] = false; deg[j]--; } } } return 1; } int main() { // freopen("in.txt", "r", stdin); int m, u, v; while(~scanf("%d%d", &n, &m)) { if(n == 0 && m == 0) break; memset(G, false, sizeof(G)); memset(deg, 0, sizeof(deg)); for(int i = 1; i <= m; i++) { scanf("%d%d", &u, &v); if(G[u][v] == false) { G[u][v] = true; deg[v]++; } } if(toposort()) printf("YES\n"); else printf("NO\n"); } return 0; }

    下面是用队列优化的,既然入度为0的才能入队列,所以判环条件就是如果所有的点都入过队列则无环。不过时间貌似还多了16ms。。

    #include <stdio.h> #include <algorithm> #include <stdlib.h> #include <string.h> #include <iostream> #include <queue> using namespace std; typedef long long LL; const int N = 1000; const int INF = 0x3f3f3f3f; int deg[N], n, cnt; bool G[N][N]; int toposort() { queue<int>que; int k = 0; for(int i = 0; i < n; i++) { if(deg[i] == 0) { que.push(i); k++; deg[i]--; } } while(!que.empty()) { int s = que.front(); que.pop(); for(int i = 0; i < n; i++) { if(G[s][i] == true) { G[s][i] = false; deg[i]--; if(deg[i] == 0) { que.push(i); k++; } } } } if(k == n) return 1; else return 0; } int main() { // freopen("in.txt", "r", stdin); int m, u, v; while(~scanf("%d%d", &n, &m)) { if(n == 0 && m == 0) break; memset(G, false, sizeof(G)); memset(deg, 0, sizeof(deg)); for(int i = 1; i <= m; i++) { scanf("%d%d", &u, &v); if(G[u][v] == false) { G[u][v] = true; deg[v]++; } } if(toposort()) printf("YES\n"); else printf("NO\n"); } return 0; }

    转载请注明原文地址: https://ju.6miu.com/read-700181.html

    最新回复(0)