题目类型 拓扑排序
题目意思
给出 n (2 <= n <= 26) 个大写字母和 m 个关系 每个关系形是"A<B"这样的格式
现在从第１个关系按顺序往后看 如果到第 i 个关系时出现矛盾则输出在第 i 个关系后矛盾了 如果到第 i 个关系时大写字母的顺序已经唯一确定那么输出确定后的序列 如果到最后依然没唯一确定顺序输出不能确定顺序
解题方法
直接按照题目意思每输入一个关系判断一下就行了
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1000;
char str[maxn][10];
vector<int>M[30];
int res[30], num[30], n, tm[30];
bool vis[30];
int topo() {
queue<int>q;
int tn = 0;
for( int i=0; i<26; i++ ) {
if(num[i] == 0 && vis[i]) q.push(i);
if(vis[i]) tn++;
tm[i] = num[i];
}
int cnt = 0;
int flag = 0;
while(!q.empty()) {
if(q.size() > 1) flag = 1; // 出现两个以上入度为0的点则没确定唯一顺序
int f = q.front(); q.pop();
res[cnt++] = f;
for( int i=0; i<M[f].size(); i++ ) {
tm[M[f][i]]--;
if(tm[M[f][i]] == 0) q.push(M[f][i]);
}
}
if(cnt == n) { // 完成排序
if(flag == 0) return 2; //唯一排序
else return 1;
}
else if(cnt != tn) return 0; //没完成排序即有冲突
else return 1; //没有唯一的顺序
}
int main() {
freopen("in", "r", stdin);
int m;
while(scanf("%d%d", &n, &m), n || m) {
for( int i=0; i<26; i++ ) num[i] = 0, M[i].clear();
memset(vis, 0, sizeof(vis));
bool flag = true;
for( int i=0; i<m; i++ ) {
scanf("%s", str[i]);
if(flag == false) continue;
num[str[i][2]-'A']++;
M[str[i][0]-'A'].push_back(str[i][2]-'A');
vis[str[i][0]-'A'] = vis[str[i][2]-'A'] = true;
int tmp = topo();
if(tmp == 0) {
flag = false;
printf("Inconsistency found after %d relations.\n", i+1);
}
else if(tmp == 2) {
flag = false;
printf("Sorted sequence determined after %d relations: ", i+1);
for( int j=0; j<n; j++ ) printf("%c", res[j]+'A');
printf(".\n");
}
}
if(flag == false) continue;
printf("Sorted sequence cannot be determined.\n");
}
return 0;
}