UVa 11686 Pick up sticks (BFS拓扑排序)

本文主要是介绍UVa 11686 Pick up sticks (BFS拓扑排序)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2733

算是一种模板题吧。。

两个发现：

1. 重复初始化queue相当费时间！最好只声明一次queue！

2. 能不用iterator就不用，这个也相当费时间！

完整代码：

/*0.732s*/#include<bits/stdc++.h>
using namespace std;
const int mx = 1000001;vector<int> edge[mx];
int indeg[mx], ans[mx];int main()
{int n, m, i, a, b, x, v, len, Size;queue<int> q;while (scanf("%d%d", &n, &m), n){for (i = 1; i <= n; ++i) edge[i].clear();memset(indeg, 0, sizeof(indeg));while (m--){scanf("%d%d", &a, &b);edge[a].push_back(b);++indeg[b]; ///入度}for (i = 1; i <= n; ++i)if (indeg[i] == 0) q.push(i);len = 0;while (!q.empty()){ans[++len] = x = q.front();q.pop();Size = edge[x].size();for (i = 0; i < Size; ++i){v = edge[x][i];--indeg[v];if (indeg[v] == 0) q.push(v);}}if (len == n) for (i = 1; i <= n; ++i) printf("%d\n", ans[i]);else puts("IMPOSSIBLE");}return 0;
}

这篇关于UVa 11686 Pick up sticks (BFS拓扑排序)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---