【ACM】UVA-10305 Ordering Tasks 【拓扑排序】

xiaoxiao2021-03-01  78

题目链接
题意分析

实现拓扑排序

解题思路

用邻接表存储有向图,按拓扑排序算法解决即可!


AC程序(C++)
/********************************** *@ID: 3stone *@ACM: UVA-10305 Ordering Tasks *@Time: 18/9/10 *@IDE: DEV C++ 5.10 *@KEY:莫要好高骛远,你先成为软微最优秀的那部分再抱怨其他!!! ***********************************/ #include<cstdio> #include<algorithm> #include<queue> using namespace std; const int maxn = 110; int N, M; struct Node{ int id, count; Node() { count = 0; } }node[maxn]; //其实直接用一个count[]数组就行 vector<int> Adj[maxn]; //邻接表 void topsort() { queue<int> Q; for(int i = 1; i <= N; i++) { //寻找入度为0的顶点 if(node[i].count == 0) Q.push(i); } int num = 0; while(!Q.empty()) { num++; //记录已经输出的结点个数 int v = Q.front(); Q.pop(); printf("%d", v); if(num == N) printf("\n"); else printf(" "); for(int i = 0; i < Adj[v].size(); i++){ //删除边,入度-1,判断 if(--node[Adj[v][i]].count == 0) Q.push(Adj[v][i]); } }//while } int main() { int a, b; while(true) { scanf("%d %d", &N, &M); if(N == 0 && M == 0) break; //初始化 邻接表 for(int i = 1; i < maxn; i++) Adj[i].clear(); //输入结点偏序 for(int i = 1; i <= M; i++) { scanf("%d %d", &a, &b); Adj[a].push_back(b); //邻接表存储 node[b].count++; //入度+1 } topsort(); //拓扑排序 } return 0; }
转载请注明原文地址: https://www.6miu.com/read-4200249.html

最新回复(0)