【C语言】 双栈排序问题

题目如下：

经典的双栈排序问题，题目很简单但是实现却很难，花了很久的时间想这道题，最后看到了一个二分图染色法的思路，最终终于解决了，二分图染色法：https://blog.****.net/linwh8/article/details/52606751

话不多说，直接上代码

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MAX 1003

bool picture[MAX][MAX];   // bipartite graph
int color[MAX];  // The color of elements
int temp[MAX];
int small[MAX];  // An array use for judge whether the two numbers obey the rule
int num; // The number of elements we want to enter
bool flag; // Make up whether the string of number can fit into  two£­stack sort

void set_color(int i, int c){
    color[i] = c;
    for (int j = 0; j < num; j++) {
        if (picture[i][j]) {
            if (color[j] == c) {
                flag = false;
            }
            if (!color[j]) {
                set_color(j, 3-c);
            }
        }
    }
}

void Creat_Picture(){
    small[num] = 0x7FFFFFFF;  // INT_MAX, you can set the number that bigger than the elements you put
    for (int i = num-1; i >= 0; i--) {
        small[i] = temp[i];
        if (small[i+1] < small[i]) {   // create the array for the rule
            small[i] = small[i+1];
        }
    }
    for (int i = 0; i < num-1; i++) {
        for (int j = i+1; j < num; j++) {
            if (temp[i] < temp[j] && small[j+1] < temp[i]) {
                picture[i][j] = picture[j][i] = 1;    // create the gragh according to the rule
            }
        }
    }
    for (int i = 0; i < num; i++) {
        if (!color[i]) {       // set the default color to 1 for the unsigned one
            set_color(i, 1);
        }
    }
}

int main()
{
    int i, j, k;
    int position;
    int total_num;// number of lines
    scanf("%d\n", &total_num);

    for(k = 0; k < total_num; k++){
        int max = -1;
        scanf("%d\n", &num);
        flag = true;
        for(i = 0; i < MAX; i++) {
            color[i] = 0;
            temp[i] = 0;
            small[i] = 0;
            for (j = 0; j < MAX; j++)
                picture[i][j] = 0;
        }
        for(i = 0; i < num; i++)
            scanf("%d", &temp[i]);
        for(i = 0; i < num; i++)
            if (temp[i] > max)
            {
                position = i;
                max = temp[i];
            }
        for(i = 0; i < num-1; i++)
            for(j = i+1; j < num; j++)
                if(position < i && temp[j] > temp[i])
                {
                    picture[i][j] = 1;
                    picture[j][i] = 1;
                }

        for (i = 0; i < num; i++)
            if (!color[i])
                set_color(i, 1);

        if (flag)
            printf("Yes\n");
        else
            printf("No\n");
    }
}