警示后人(如果你得40分)
  • 板块P1347 排序
  • 楼主Molie
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/11/22 20:31
  • 上次更新2023/11/22 22:45:02
查看原帖
警示后人(如果你得40分)
732415
Molie楼主2023/11/22 20:31

注意题意:如果数据 构成条件不足与矛盾的话,优先输出矛盾。 换句人话说:你不要在拓扑排序里判断出了条件不足,就直接输返回条件不足的信号,还得判断后面是否会构成矛盾。反正对于一条数据,矛盾优先级更在前面,

//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;
	}

2023/11/22 20:31
加载中...