LG1155【NOIp2008】双栈排序 <二分图染色>

Problem

【NOIp2008】双栈排序

题目描述

最近在研究一个有趣的排序问题。如图所示，通过个栈和，希望借助以下种操作实现将输入序列升序排序。
操作: 如果输入序列不为空，将第一个元素压入栈
操作: 如果栈不为空，将栈顶元素弹出至输出序列
操作: 如果输入序列不为空，将第一个元素压入栈
操作: 如果栈不为空，将栈顶元素弹出至输出序列
如果一个的排列可以通过一系列操作使得输出序列为，就称是一个“可双栈排序排列”。例如就是一个“可双栈排序序列”，而不是。下图描述了一个将排序的操作序列：

当然，这样的操作序列有可能有几个，对于上例，是另外一个可行的操作序列。希望知道其中字典序最小的操作序列是什么。

输入输出格式

输入格式：
输入文件的第一行是一个整数。
第二行有个用空格隔开的正整数，构成一个的排列。
输出格式：
输出文件共一行，如果输入的排列不是“可双栈排序排列”，输出数字；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。

输入输出样例

输入样例#1

1
2

4
1 3 2 4

输出样例#1

1	a b a a b b a b

输入样例#2

1
2

4
2 3 4 1

输出样例#2

输入样例#3

1
2

3
2 3 1

输出样例#3

1	a c a b b d

说明

的数据满足：
的数据满足：
的数据满足：

标签：二分图染色

Solution

一道很有意思的联赛题。
对于任意两数，若有，为了使最先出栈，那么和一定在之后出栈，若顺次放进同一个栈，那么必然在之前出栈，不满足题意。因此遇到这种情况和一定分别放入两个栈中。
据此，只要存在，有，那么和一定在不同栈中。这样就构成了一个二分图。
扫描一遍，确定那些数对不能在同一栈中，确定互斥关系。若不能构成二分图，那么就不可排序。否则在判断过程中染色，确定不同数在哪个栈中，模拟排序过程，每次等到当前排到的数进栈后把能出栈的都出栈。

Code

#include <bits/stdc++.h>
#define MAX_N 1000
using namespace std;
vector <int> G[MAX_N+5];
int n, a[MAX_N+5], mi[MAX_N+5], col[MAX_N+5];
void DFS(int u) {
    for (auto v : G[u]) {
        if (!col[v])	col[v] = -col[u], DFS(v);
        if (col[u] == col[v]) {puts("0");	exit(0);}
    }
}
void prt() {
    int cur = 1;	stack <int> sa, sb;
    for (int i = 1; i <= n; i++) {
        if (col[i] == 1)	putchar('a'), putchar(' '), sa.push(a[i]);
        else	putchar('c'), putchar(' '), sb.push(a[i]);
        for (; !sa.empty() && sa.top() == cur; sa.pop(), cur++)	putchar('b'), putchar(' ');
        for (; !sb.empty() && sb.top() == cur; sb.pop(), cur++)	putchar('d'), putchar(' ');
        for (; !sa.empty() && sa.top() == cur; sa.pop(), cur++)	putchar('b'), putchar(' ');
    }
}
int main() {
    scanf("%d", &n);	for (int i = 1; i <= n; i++)	scanf("%d", a+i);
    mi[n+1] = 0x3f3f3f3f;	for (int i = n; i; i--)	mi[i] = min(a[i], mi[i+1]);
    for (int i = 1; i <= n; i++)	for (int j = i+1; j <= n; j++)
        if (a[i] < a[j] && mi[j+1] < a[i])	G[i].push_back(j), G[j].push_back(i);
    for (int i = 1; i <= n; i++)	if (!col[i])	col[i] = 1, DFS(i);	prt();
    return 0;
}