Bailian4084 拓撲排序
問題簡述:(略)
問題分析:拓撲排序的模闆題,但是這個題需要按一定順序輸出結果。
程式說明:用數組din[]存儲各個結點的入度。由于需要按指定順序輸出結果,需要用優先隊列給結點排隊。
參考連結:(略)
題記:(略)
AC的C++語言程式如下:
/* Bailian4084 拓撲排序 */
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
vector<int> e[N + 1];
int n, m, din[N + 1], ans[N], cnt;
int toposort()
{
priority_queue<int, vector<int>, greater<int>> q;
for(int i = 1; i <= n; i++)
if(din[i] == 0) q.push(i);
cnt = 0;
while(!q.empty()) {
int u = q.top();
q.pop();
ans[cnt++] = u;
for(int i = 0; i < (int) e[u].size(); i++) {
int v = e[u][i];
if(--din[v] == 0) q.push(v);
}
}
return cnt;
}
int main()
{
while(~scanf("%d%d", &n, &m)) {
for(int i = 1; i <= n; i++) e[i].clear();
memset(din, 0, sizeof(din));
for(int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
e[u].push_back(v);
din[v]++;
}
if(toposort() == n)
for(int i = 0; i < n; i++) printf("v%d ", ans[i]);
printf("\n");
}
return 0;
}