注意题意:如果数据 构成条件不足与矛盾的话,优先输出矛盾。 换句人话说:你不要在拓扑排序里判断出了条件不足,就直接输返回条件不足的信号,还得判断后面是否会构成矛盾。反正对于一条数据,矛盾优先级更在前面,
//1条件成立 0条件不足 -1条件矛盾
static int topSort() {
int ans = 1;
int cnt = 0;//入度为0的点
queue.clear();
Arrays.fill(vis, false);
for (int i = 1; i <= n; ++i) {
if (temp[i] == 0) {
cnt++;
queue.add(i);
vis[i] = true;
}
}
sb.delete(0, sb.length());
//没有入度为0的点,一定矛盾
if (cnt == 0) return -1;
if (cnt > 1) {
ans = 0;//这里就不能写成return 0,因为后面可能判断出矛盾
}
cnt = 0;//记录出队次数
while (!queue.isEmpty()) {
int u = queue.poll();
sb.append((char) ('A' + u - 1));
cnt++;
int count = 0;//记录这个点让多少个点变0
for (int v : nodes.get(u)) {
temp[v]--;
if (temp[v] == 0 && (!vis[v])) {
queue.add(v);
count++;
vis[v] = true;
}
}
if (count > 1) {
ans = 0;
}
}
if (cnt < n) return -1;
return ans;
}