LG1410 子序列 二分图判定

问题描述

LG1410

题解

如果\(i<j,a_j \le a_i\)，那么他它们不能在一个上升序列中。

于是在\(i,j\)之间建边，看建出来的图是不是二分图即可。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

const int maxn=2007;

int n,a[maxn];
int Head[maxn],to[maxn*maxn],tot=1,Next[maxn*maxn];

void add(int x,int y){
    to[++tot]=y,Next[tot]=Head[x],Head[x]=tot;
}

int col[maxn];
bool flag;

void dfs(int x,int cl){
    col[x]=cl;
    for(int i=Head[x];i;i=Next[i]){
        int y=to[i];
        if(col[y]){
            if(col[y]!=3-cl){
                flag=1;return;
            }
            continue;
        }
        dfs(y,3-cl);
    }
}

int main(){
    while((~scanf("%d",&n))&&n){
        for(int i=1;i<=n;i++) read(a[i]);memset(Head,0,sizeof(Head));
        memset(Next,0,sizeof(Next));tot=0;memset(col,0,sizeof(col));
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(a[j]<=a[i]){
                    add(i,j);add(j,i);
                }
            }
        }
        flag=0;
        for(int i=1;i<=n;i++){
            if(!col[i]) dfs(i,1);
            if(flag) break;
        }
        if(!flag) puts("Yes!");
        else puts("No!");
    }
    return 0;
}