mem oid div eof vector sort ++ clear 链式前向星
题意:在一幅竞赛图中排序,要求同名次按字典序排序。
解题关键:拓扑排序模板题
1、邻接表建图
- #include < cstdio > #include < cstring > #include < algorithm > #include < cstdlib > #include < iostream > #include < cmath > #include < vector > #include < queue > using namespace std;
- typedef long long ll;
- const int N = 510;
- vector < int > g[N];
- int deg[N],
- seq[N];
- int n,
- m,
- u,
- v,
- tol;
- priority_queue < int,
- vector < int > ,
- greater < int > >q; //因为是按字典序的,要注意重边的情况
- void toposort() {
- for (int i = 1; i <= n; i++) if (!deg[i]) q.push(i);
- tol = 0;
- while (q.size()) {
- int u = q.top();
- q.pop();
- seq[tol++] = u;
- for (int i = 0; i < g[u].size(); i++) {
- int v = g[u][i];
- deg[v]--;
- if (!deg[v]) q.push(v);
- }
- }
- }
- int main() {
- while (scanf("%d%d", &n, &m) != EOF) {
- memset(deg, 0, sizeof deg);
- for (int i = 1; i <= n; i++) g[i].clear();
- for (int i = 1; i <= m; i++) {
- scanf("%d%d", &u, &v);
- g[u].push_back(v);
- deg[v]++;
- }
- toposort();
- for (int i = 0; i < tol; i++) printf("%d%c", seq[i], i == tol - 1 ? ‘\n‘: ‘‘);
- }
- return 0;
- }
2、链式前向星建图
- #include < cstdio > #include < cstring > #include < algorithm > #include < cstdlib > #include < iostream > #include < cmath > #include < vector > #include < queue > using namespace std;
- typedef long long ll;
- const int N = 510;
- priority_queue < int,
- vector < int > ,
- greater < int > >q; //因为是按字典序的,要注意重边的情况
- int deg[N],
- seq[N];
- int n,
- m,
- u,
- v,
- tol;
- struct Edge {
- int nxt;
- int to;
- int w;
- }
- e[N];
- int head[N],
- cnt;
- void add_edge(int u, int v) {
- e[cnt].to = v;
- e[cnt].nxt = head[u];
- head[u] = cnt++;
- }
- void toposort() {
- for (int i = 1; i <= n; i++) if (!deg[i]) q.push(i);
- tol = 0;
- while (q.size()) {
- int u = q.top();
- q.pop();
- seq[tol++] = u;
- for (int i = head[u]; i != -1; i = e[i].nxt) {
- int v = e[i].to;
- deg[v]--;
- if (!deg[v]) q.push(v);
- }
- }
- }
- int main() {
- while (scanf("%d%d", &n, &m) != EOF) {
- memset(deg, 0, sizeof deg);
- memset(head, -1, sizeof head);
- cnt = 0;
- for (int i = 1; i <= m; i++) {
- scanf("%d%d", &u, &v);
- add_edge(u, v);
- deg[v]++;
- }
- toposort();
- for (int i = 0; i < tol; i++) printf("%d%c", seq[i], i == tol - 1 ? ‘\n‘: ‘‘);
- }
- return 0;
- }
[hdu1285]确定比赛名次(拓扑排序)
来源: http://www.bubuko.com/infodetail-2347294.html