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

题目链接

题意分析

实现拓扑排序

解题思路

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

---

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; }