题目传送门

 /*
给出n个字符串,求是否有一个“字典序”使得n个字符串是从小到大排序
拓扑排序
详细解释:http://www.2cto.com/kf/201502/374966.html
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
using namespace std; const int MAXN = 1e6 + ;
const int INF = 0x3f3f3f3f;
char s[][];
int in[];
bool lin[][];
char ans[]; bool TopoSort(void)
{
queue<int> q;
int cnt = ;
for (int i=; i<=; ++i)
{
if (in[i] == )
{
q.push (i);
ans[cnt++] = 'a' + i - ;
}
}
while (!q.empty ())
{
int now = q.front (); q.pop ();
for (int i=; i<=; ++i)
{
if (lin[now][i])
{
in[i]--;
if (in[i] == )
{
q.push (i);
ans[cnt++] = 'a' + i - ;
}
}
}
}
ans[] = '\0';
if (cnt < ) return false;
else return true;
} int main(void)
{
//freopen ("C.in", "r", stdin); int n; while (~scanf ("%d", &n))
{
memset (lin, false, sizeof (lin));
memset (in, , sizeof (in));
for (int i=; i<=n; ++i)
{
scanf ("%s", &s[i]);
} bool flag = true;
for (int i=; i<=n- && flag; ++i)
{
int len1 = strlen (s[i]);
int len2 = strlen (s[i+]);
bool ok = false;
for (int j=; j<=len1- && j<=len2- && !ok; ++j)
{
if (s[i][j] != s[i+][j])
{
ok = true;
if (!lin[s[i][j]-'a'+][s[i+][j]-'a'+])
{
in[s[i+][j]-'a'+]++;
lin[s[i][j]-'a'+][s[i+][j]-'a'+] = true;
}
}
}
if (!ok && len1 > len2) flag = false;
} if (!flag) puts ("Impossible");
else
{
flag = TopoSort ();
if (!flag) puts ("Impossible");
else printf ("%s\n", ans);
}
} return ;
}

最新文章

  1. SQL Server 2008 R2企业版开发版等版本下载 (转载)
  2. DHCP snooping
  3. MySQL 复制介绍及搭建
  4. Xcode因为证书问题经常报的那些错
  5. JAVA 多线程和并发学习笔记(一)
  6. 如何起草你的第一篇科研论文——应该做&amp;避免做
  7. Scripting Languages
  8. linux下解压命令大全(转载)
  9. 对象的继承关系在数据库中的实现方式和PowerDesigner设计
  10. 关于php的一些开源程序
  11. c++ primer plus 习题答案(5)
  12. ASP.Net MVC 数据处理
  13. 51nod 1228、1258 序列求和
  14. 利用jquery操作隐藏table某一列
  15. jQuery中的CSS(二)
  16. [九省联考2018]一双木棋chess
  17. Harmonic Value Description HDU - 5916
  18. 语法分析器初步学习——LISP语法分析
  19. Sqlserver数据库中,跨权限执行语句
  20. 使用 IntraWeb (9) - JavaScript

热门文章

  1. Activity切换后,如i何保存上一个Activit的状态
  2. ubuntu同步系统时间命令
  3. [POJ1007]DNA Sorting
  4. 在pc游览器端模拟移动端幻灯片
  5. facedetect
  6. Jackson 框架,轻易转换JSON
  7. 配置caffe的python环境时make pycaffe提示fatal error: numpy/arrayobject.h No such file or directory解决方法
  8. Linux 制作ftp远程yum仓库
  9. BZOJ 1058
  10. 【转】基于注解的SpirngMVC简单介绍