deployment laravel4 jwt chartjs gtk Browserify 建造师报考条件 vue社区 angular视频教程 微信小游戏开发视频 多商户商城模板 jq获取元素 oracle无效的列索引 mysql时间戳转时间 mysql更新 python开发环境 python学习教程 java数组反转 java类型 java基础课程 java中基本数据类型 怎么安装java环境 java替换字符 嵌入式开发教程 登录界面html 服务器操作系统下载 win7loader navicat注册机 骰子表情 掌门一对一下载 jarsigner cdr怎么画波浪线 directx卸载 战法装备 苹果手机怎么看内存 大势至usb控制系统 微信小程序循环 win10工作组 winrar无广告版 ps平面设计基础教程
当前位置: 首页 > 学习教程  > 编程语言

51nod 2664 字母表(DAG)

2020/12/28 19:36:00 文章标签:

2664 字母表 给你n个按照特殊字典序排好序的单词,你来设计一种字典序,使得按照你的这种字典序来排序这n个单词,得到的结果与给出的单词序列相同。如果做不到,请输出Impossible。例如6个单词: aa ac ab ba ca 不存在任…

2664 字母表

给你n个按照特殊字典序排好序的单词,你来设计一种字典序,使得按照你的这种字典序来排序这n个单词,得到的结果与给出的单词序列相同。如果做不到,请输出Impossible。例如6个单词:
aa
ac
ab
ba
ca
不存在任何字典序,可以满足按照该方法排序,能够得到上面的顺序。我们默认空字符是字典序小的,所以a < aa。

输入

第一行:1个数n(1 ≤ n ≤ 100)。
后面n行:每行一个单词,只包括a-z这26个小写字符,单词长度L<= 100。

输出

输出共26个字母,对应一个a-z的排列。如果做不到,请输出Impossible。

输入样例

3
rivest
shamir
adleman

输出样例

bcdefghijklmnopqrsatuvwxyz

题解

就是按照要求建图,然后跑个DAG,不过有个坑,就是输入可能存在负环(第31组样例),拓扑排序里面得判一下。(真是不懂为啥答案错误给我报运行错误…本地完美运行)

实现代码
#include <bits/stdc++.h>

using namespace std;
int N;
// 前驱数量
int mp[30][30];
int indegree[30];
// 保存拓扑排序
int q[310];

void dag(int n) {
    int t = 0, m = -1;
    for (int j = 1; j <= n; j++) {
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) {
                m = i;
                break;
            }
        }
        // 注意该题输入可能有环
        if (m == -1) {
            cout << "Impossible\n";
            return;
        }
        q[t++] = m;
        indegree[m] = -1;
        for (int i = 1; i <= n; i++) {
            if (mp[m][i] == 1) {
                indegree[i]--;
            }
        }
        m = -1;
    }
    for (int i = 0; i < n; i++) {
        cout << char(q[i] + 'a' - 1);
    }
    cout << endl;
}

int main() {
    cin >> N;
    string s;
    cin >> s;
    int flag = 1;
    N--;
    while (N--) {
        string ss;
        cin >> ss;
        if (flag == 0) {
            continue;
        }
        for (int i = 0; i < min(s.length(), ss.length()); i++) {
            int a = s[i] - 'a' + 1;
            int b = ss[i] - 'a' + 1;
            if (a != b) {
                if (mp[a][b] == 0) {
                    mp[a][b] = 1;
                    mp[b][a] = -1;
                    // 记录前驱节点
                    indegree[b]++;
                } else if (mp[a][b] == -1) {
                    flag = 0;
                }
                break;
            } else {
                if (i == min(s.length(), ss.length()) - 1) {
                    if (s.length() > ss.length()) {
                        flag = 0;
                    }
                }
            }
        }
        s = ss;
    }
    if (flag == 0) {
        cout << "Impossible\n";
        return 0;
    }
    topology(26);
    return 0;
}

本文链接: http://www.dtmao.cc/news_show_550315.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?