拓扑排序 Codeforces Round #290 (Div. 2) C. Fox And Names
发布日期:2021-08-24 18:36:04 浏览次数:40 分类:技术文章

本文共 1882 字,大约阅读时间需要 6 分钟。

 

1 /*  2     给出n个字符串,求是否有一个“字典序”使得n个字符串是从小到大排序  3     拓扑排序  4     详细解释:http://www.2cto.com/kf/201502/374966.html  5 */  6 #include 
7 #include
8 #include
9 #include
10 #include
11 #include
12 #include
13 #include
14 #include
15 #include
16 using namespace std; 17 18 const int MAXN = 1e6 + 10; 19 const int INF = 0x3f3f3f3f; 20 char s[110][110]; 21 int in[110]; 22 bool lin[27][27]; 23 char ans[27]; 24 25 bool TopoSort(void) 26 { 27 queue
q; 28 int cnt = 0; 29 for (int i=1; i<=26; ++i) 30 { 31 if (in[i] == 0) 32 { 33 q.push (i); 34 ans[cnt++] = 'a' + i - 1; 35 } 36 } 37 while (!q.empty ()) 38 { 39 int now = q.front (); q.pop (); 40 for (int i=1; i<=26; ++i) 41 { 42 if (lin[now][i]) 43 { 44 in[i]--; 45 if (in[i] == 0) 46 { 47 q.push (i); 48 ans[cnt++] = 'a' + i - 1; 49 } 50 } 51 } 52 } 53 ans[26] = '\0'; 54 if (cnt < 26) return false; 55 else return true; 56 } 57 58 int main(void) 59 { 60 //freopen ("C.in", "r", stdin); 61 62 int n; 63 64 while (~scanf ("%d", &n)) 65 { 66 memset (lin, false, sizeof (lin)); 67 memset (in, 0, sizeof (in)); 68 for (int i=1; i<=n; ++i) 69 { 70 scanf ("%s", &s[i]); 71 } 72 73 bool flag = true; 74 for (int i=1; i<=n-1 && flag; ++i) 75 { 76 int len1 = strlen (s[i]); 77 int len2 = strlen (s[i+1]); 78 bool ok = false; 79 for (int j=0; j<=len1-1 && j<=len2-1 && !ok; ++j) 80 { 81 if (s[i][j] != s[i+1][j]) 82 { 83 ok = true; 84 if (!lin[s[i][j]-'a'+1][s[i+1][j]-'a'+1]) 85 { 86 in[s[i+1][j]-'a'+1]++; 87 lin[s[i][j]-'a'+1][s[i+1][j]-'a'+1] = true; 88 } 89 } 90 } 91 if (!ok && len1 > len2) flag = false; 92 } 93 94 if (!flag) puts ("Impossible"); 95 else 96 { 97 flag = TopoSort (); 98 if (!flag) puts ("Impossible"); 99 else printf ("%s\n", ans);100 }101 }102 103 return 0;104 }

 

转载于:https://www.cnblogs.com/Running-Time/p/4366709.html

转载地址:https://blog.csdn.net/weixin_33831196/article/details/93263386 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:map Codeforces Round #Pi (Div. 2) C. Geometric Progression
下一篇:Codeforces Round #320 (Div. 2) [Bayan Thanks-Round]

发表评论

最新留言

很好
[***.229.124.182]2024年03月02日 11时02分34秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java网络编程期末试题_java网络编程面试题【其中一小部分】 2019-04-21
estore java_estore2 - WEB源码|JSP源码/Java|源代码 - 源码中国 2019-04-21
java如何做表单校验_微信小程序实现表单校验功能 2019-04-21
matlab dwt2(),MATLAB小波变换指令及其功能介绍(超级有用) 2019-04-21
php sequelize,egg.js整合数据库ORM框架Sequelize 2019-04-21
php同时打开2个数据库,thinkphp3.2同时连接两个数据库的简单方法 2019-04-21
centos 开发php扩展,centos 安装php扩展redis 2019-04-21
php+跑buth,php 中函数获取可变参数的方法, 这个语法有点像 golang 语言中的 2019-04-21
cms 单点登录 php,Yii2 中实现单点登录的方法 2019-04-21
oracle自己运行,创建Oracle自动执行Job 2019-04-21
oracle报错00020,oracle启动 ORA-00020: maximum number of processes (%s) exceeded错误 2019-04-21
chmod 赋权所有_chmod 权限 命令详细用法 2019-04-21
html代码翻译_[译]您知道 HTML 的键盘标签吗? 2019-04-21
html抽奖代码_JavaScript高手之路:封装抽奖效果 2019-04-21
hadoop 3.3 一直停留在running wordcount_蛋价持续下跌,今日跌破3.3元大关!深秋季节价格还能反弹吗?... 2019-04-21
的流程图做完后如何保存_2019超火的半永久眉是哪款?做完后我们如何护理?... 2019-04-21
去除logo 高德地图api_深圳品牌logo升级如何保持原型的同时更具创新? 2019-04-21
二重积分转换成极坐标_二重积分转换极坐标r的范围如何确定? 2019-04-21
python中倒背如流_八字基础知识--倒背如流篇 2019-04-21
以太坊地址和公钥_以太坊地址是什么 2019-04-21