Codeforces 1159E（拓扑序、思路）

要点

序列上各位置之间的关系常用连边的手段转化为图的问题。
经过一番举例探索不难发现当存在两条有向边交叉时是非法的。
-1是模糊的，也就是填多少都可以，那为了尽量避免交叉我们贪心地让它后面那个连它就行了。
看到一个很简短的dfs做法。从右向左一探到底，不行时回溯，直到可行后再探。

const int maxn = 5e5 + 5;

int T, n, a[maxn], ans[maxn], C;

int dfs(int now) {

	int i = now;

	while (i > 1 && (a[i - 1] == now || a[i - 1] == -1))

		i = dfs(i - 1);

	ans[now] = ++C;

	return i;

}

int main() {

	for (read(T); T--; C = 0) {

		read(n);

		rep(i, 1, n)	read(a[i]);

		if (dfs(n + 1) > 1)

			puts("-1");

		else {

			rep(i, 1, n)

				printf("%d%c", ans[i], " \n"[i == n]);

		}

	}

	return 0;

}

巴特西

Codeforces 1159E（拓扑序、思路）

要点

最新文章

热门文章