官方题解——烦人的依赖

烦人的依赖

http://www.nowcoder.com/questionTerminal/e4a778ab113240c5bf8c3ba80a5a8482

B - 烦人的依赖

​软件的依赖关系可以看作一个有向图,而软件安装顺序就是求有向图的一个拓扑排序。注意题目中要求按照字典序排序,因此拓扑排序中要用优先队列。对于字符串的处理,可以先映射成整数,再做拓扑排序。
有的同学反映超时,可以试试看unordered_map,比map要少个log。

#include <bits/stdc++.h>
#include <cstring>
#define MAXN 30005
using namespace std;

int T, n, m, u, v, cnt=0, an;
string s, t;
string soft[MAXN];
int in[MAXN];
vector<int> edge[MAXN];
priority_queue<int> Q;
unordered_map<string, int> s2n;
int ans[MAXN];

void init(int n) {
    memset(in, 0, sizeof(in));
    while(!Q.empty())
        Q.pop();
    s2n.clear();
    for (int i=1; i<=n; ++i)
        edge[i].clear();
    an=0;
}

void solve() {
    scanf("%d%d", &n, &m);
    init(n);
    for (int i=1; i<=n; ++i)
        cin >> soft[i];
    sort(soft+1, soft+n+1, greater<string>());
    for (int i=1; i<=n; ++i)
        s2n[soft[i]]=i;
    for (int i=1; i<=m; ++i) {
        cin >> s >> t;
        ++in[s2n[t]];
        edge[s2n[s]].push_back(s2n[t]);
    }
    for (int i=1; i<=n; ++i) 
        if (!in[i]) Q.push(i);
    while(!Q.empty()) {
        u=Q.top(); Q.pop();
        ans[++an]=u;
        int len=edge[u].size();
        for (int i=0; i<len; ++i) {
            v=edge[u][i];
            if (!(--in[v])) Q.push(v);
        }
    }
    printf("Case #%d:\n", ++cnt);
    if (an!=n) {
        printf("Impossible\n");
        return;
    }
    for (int i=1; i<=an; ++i) {
        printf("%s\n", soft[ans[i]].c_str());
    }
}

int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}
全部评论
好的
点赞 回复 分享
发布于 2020-07-23 17:51
[Error] 's2n' was not declared in this scope [Error] 'unordered_map' does not name a type兄弟你这个代码粘到DEVc++里报这个错误是怎么回事呀
点赞 回复 分享
发布于 2020-05-28 17:21
太巧妙了,我当时做的时候想不起来怎么处理按字典序排列这回事,原来要用优先队列❤❤❤
点赞 回复 分享
发布于 2020-05-24 08:57

相关推荐

不愿透露姓名的神秘牛友
07-15 17:09
点赞 评论 收藏
分享
07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
评论
5
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务