拓扑排序 Codeforces Round #290 (Div. 2) C. Fox And Names

题目传送门

 /*
给出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 ;
}
上一篇:IOS 遍历未知对象的属性和方法


下一篇:android - 调试