两个很经典的拓扑排序题目POJ3687+HDU1285

一、题目链接

　　HDU：http://acm.hdu.edu.cn/showproblem.php?pid=1285

二、思路

　　这两题题意非常相似，但是，做法却十分不同。不同的地方是，POJ题目要求按编号顺序输出排名，在答案不唯一的情况下，编号小的排名尽量靠前(即编号的更小的结点的排名优先输出)；HDU题目要求按排名顺序输出编号，在答案不唯一的情况下(排名相同的情况下)，编号小的尽量靠前。这两个不同的输出感觉是一个意思。但是，做法却不相同。实际上，这两题的共同点就是，在答案不唯一的情况下，输出字典序最小的。

　　做法上，POJ题目是反向建边+编号大根堆。优先取入度为0的编号大的点，以保证编号小的顶点排名尽可能小。而HDU是正向建边+编号小根堆。

三、注意事项

　　输入时，写成

while(~scanf("%d%d", &n, &m))//即while(scanf("%d%d", &n, &m) != EOF)

　　这样写，就要记得做初始化(容器clear, pop, 数组memset)操作，但是保险。但是，也不是绝对的。如果发生超时的时候，可尝试修改这个地方为如下代码，以节省初始化产生的耗时（因为数组、容器什么的一般都写成全局变量）：

scanf("%d%d", &n, &m); //只读一个样例

四、源代码

　　POJ3687

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int n, m;
vector<];
priority_queue<int> que;
], deg[];

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int T, a, b;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        memset(deg, , sizeof(deg));
        ; i <= n; ++i)G[i].clear();
        while(!que.empty())que.pop();
        ; j <= m; ++j) {
            scanf("%d%d", &a, &b);
            if(find(G[b].begin(), G[b].end(), a) == G[b].end()) {
                G[b].push_back(a);
                deg[a]++;
            }
        }

        ; i <= n; ++i) {
            )que.push(i);
        }
        int idx = n;
        while(!que.empty()) {
            int top = que.top();
            que.pop();
            ans[top] = idx--;
            ; i < G[top].size(); ++i) {
                int to = G[top][i];
                deg[to]--;
                )que.push(to);
            }
        }
        )puts("-1");
        ; i <= n; ++i)
            printf("%d%c", ans[i], i == n ? '\n' : ' ');

    }
    ;
}

　　HDU1285

#include<bits/stdc++.h>
using namespace std;
];
vector<], ans;
priority_queue<int, vector<int>, greater<int> > que;
int main() {
    int a, b;
    while(~scanf("%d%d", &n, &m)) {
        memset(deg, , sizeof(deg));
        ; i < ; ++i)G[i].clear();
        while(!que.empty())que.pop();
        ans.clear();

        ; i <= m; ++i) {
            scanf("%d%d", &a, &b);
            if(find(G[a].begin(), G[a].end(), b) == G[a].end()) {
                G[a].push_back(b);
                deg[b]++;
            }
        }
        ; i <= n; ++i) {
            )que.push(i);
        }
        while(!que.empty()) {
            int top = que.top();
            que.pop();
            ans.push_back(top);
            ; i < G[top].size(); ++i) {
                int to = G[top][i];
                deg[to]--;
                )que.push(to);
            }
        }
        ;i < ans.size();++i)printf( ? '\n':' ');
    }
    ;
}

巴特西

两个很经典的拓扑排序题目POJ3687+HDU1285

最新文章

热门文章