AcWing 343. 排序(Java注释版)
原题链接
简单
Java代码
(floyd传递闭包) $O(n^3)$
参考文献
小呆呆代码
Java 代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N = 26;
static int[][] g = new int[N][N];
static int[][] dist = new int[N][N];
static int n,m;
static Pair[] level = new Pair[N];
static void floyd()
{
dist = g.clone();
for(int k = 0;k < n;k ++)
for(int i = 0;i < n;i ++)
for(int j = 0;j < n;j ++)
{
//i 连接了 k,k 连接了 j,则 i 连接了 j
if(dist[i][k] == 1 && dist[k][j] == 1)
{
dist[i][j] = 1;
}
}
}
static int check()
{
//有矛盾,自己不可能小于自己,例如 A < B,B < A,则 A < A,矛盾
for(int i = 0;i < n;i ++) if(dist[i][i] == 1) return 2;
//没有矛盾,但是不能确定两两之间的关系
for(int i = 0;i < n;i ++)
for(int j = 0;j < i;j ++)
{
if((dist[i][j] == 0 && dist[j][i] == 0)) return 0;
}
//可以确定两两之间的关系
return 1;
}
//升序排列所有变量,这里指的不是按照ABCD字典序,而是按照大小关系B<A<C,排好序是BAC
static String getSequence()
{
for(int i = 0;i < n;i ++) level[i] = new Pair((char)('A' + i),0);
for(int i = 0;i < n;i ++)
for(int j = 0;j < i;j ++)
{
//dist[i][j]不为1,对称的一边一定为1
if(dist[i][j] == 1) level[j].d ++;
else level[i].d ++;
}
Arrays.sort(level,0,n);
String res = "";
for(int i = 0;i < n;i ++)
{
res += level[i].c;
}
return res;
}
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);
int type = 0,t = 0; // type - 0:不确定,1:唯一确定,2:矛盾
while(m -- > 0)
{
char[] charArray = scan.next().toCharArray();
if(type > 0) continue;
int a = charArray[0] - 'A', b = charArray[2] - 'A';
g[a][b] = 1;//表示a < b
floyd();
type = check();
//t是迭代次数
t ++;
}
if (type == 0) System.out.println("Sorted sequence cannot be determined.");
else if (type == 2) System.out.println("Inconsistency found after " + t + " relations.");
else
{
System.out.println("Sorted sequence determined after " + t + " relations: " + getSequence() + ".");
}
}
}
}
class Pair implements Comparable<Pair>
{
char c ;//当前字符
int d;
Pair(char c,int d)
{
this.c = c;
this.d = d;
}
@Override
public int compareTo(Pair o) {
// TODO 自动生成的方法存根
return Integer.compare(d, o.d);
}
}