floyd实现传递闭包
d = g.clone();
for (int k = 0 ; k < n ; k ++ )
for (int i = 0 ; i < n ; i ++ )
for (int j = 0 ; j < n ; j ++ )
if (d[i][k] == 1 && d[k][j] == 1)
d[i][j] = 1;
//d[i][j] |= (d[i][k] & d[k][j]);
思路:
1、如果有矛盾，表示有传递闭包d[i][i] == 1
2、如果有唯一确定的关系，表示对于任意i != j，都存在d[i][j] == 1 / d[j][i] == 1
3、没有矛盾，并且没有唯一确定的关系
代码实现
import java.util.*;
public class Main{
static int N = 26;
static int n,m;
static int[][] g = new int[N][N];//g表示两个数之间有没有边
static int[][] d = new int[N][N];//d表示传递闭包
static boolean[] st = new boolean[N];//输出时候用到的判重数组
//folyd实现传递闭包
public static void floyd(){
//进行传递闭包前的初始化，将g拷贝给d
d = g.clone();
for (int k = 0 ; k < n ; k ++ )
for (int i = 0 ; i < n ; i ++ )
for (int j = 0 ; j < n ; j ++ )
if (d[i][k] == 1 && d[k][j] == 1)
d[i][j] = 1;
//d[i][j] |= (d[i][k] & d[k][j]);
}
//判断所有字母关系的情况
public static int check(){
//判断所有数，如果有相同的一个数之间有边，那么就表示有矛盾，返回2
for (int i = 0 ; i < n ; i ++ )
if (d[i][i] == 1)
return 2;
//如果其中任意两个不相等的数之间没有边，那么说明还没有确定好关系，返回0
for (int i = 0 ; i < n ; i ++ )
for (int j = 0 ; j < i ; j ++ )
if (d[i][j] == 0 && d[j][i] == 0)
return 0;
//能够执行到这里，表示已经确定好关系了，直接返回1
return 1;
}
//输出函数，取出最小值
public static char get_min(){
//枚举所有数，判断哪些数还没有被输出
for (int i = 0 ; i < n; i ++ ){
if (!st[i]){ //如果这个数还没有被输出的话
boolean flag = true;
//枚举所有数，如果这个点没有被标记过，并且，j指向i是1，
//表示有数比i小，所以flag标记成false，然后break
for (int j = 0 ; j < n ; j ++ ){
if (!st[j] && d[j][i] == 1){
flag = false;
break;
}
}
//如果flag是true表示没有点指向i，那么i是最小值，那么返回i，记得转化成char
if (flag){
st[i] = true;
return (char)(i + 'A');
}
}
}
return ' '; //不执行
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
while (true){
n = scan.nextInt();
m = scan.nextInt();
if (n == 0 && m == 0) break;
//多组测试数据，每一次都进行初始化，防止干扰
for (int i = 0 ; i < N ; i ++ ) Arrays.fill(g[i],0);
//type: 0表示不能确定关系;1表示有矛盾;2表示有唯一确定的关系
//t表示判断了几条之后才确定的
int type = 0,t = 0;
//输入m组数据
for (int i = 1 ; i <= m ; i ++ ){
String str = scan.next();
int a = str.charAt(0) - 'A';
int b = str.charAt(2) - 'A';
//type如果是0，表示现在还没有确定关系，那么就继续执行
if (type == 0){
g[a][b] = 1; //a与b之间有一条边
floyd(); //传递闭包
type = check(); //判断一下现在的关系
if (type != 0) t = i; //如果当前的关系已经找到，那么将当前执行的次数i赋值给t
}
}
//如果type等于0，说明没有确定关系，直接输出
if (type == 0) System.out.println("Sorted sequence cannot be determined.");
//如果type等于2，表示有矛盾，输出相关枚举次数t
else if (type == 2) System.out.printf("Inconsistency found after %d relations.\n",t);
//最后如果type等于1，表示没有矛盾，有唯一确定的关系
else {
//多组测试数据，每一次都进行清空
Arrays.fill(st,false);
//先输出前缀
System.out.printf("Sorted sequence determined after %d relations: ",t);
//判断一下所有数，每一次输出最小值
for (int i = 0 ; i < n ; i ++ ) System.out.print(get_min());
System.out.printf(".\n");
}
}
}
}
