Uva(1391)(Astronauts )

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn = 100001;
int n,m;
int total;
int age[maxn];

struct twosat{
    int n;
    vector<int> G[maxn*2];//存边
    bool mark[maxn*2];
     int S[maxn*2];//用来反悔标记的栈
        int c;

bool dfs(int x){
    if(mark[x^1])return false;//如果另一个已经标记，说明矛盾，无解
    if(mark[x])return true;//如果该点已经标记，返回有解
    mark[x] = true;
    S[c++] = x;//栈中记录一路过来的点，方便无解的时候“回溯”
    for(int i=0;i<G[x].size();i++)
        if(!dfs(G[x][i]))return false;
    return true;
}

void init(int n){
    this->n = n;
    for(int i=0;i<n*2;i++)G[i].clear();
        memset(mark,0,sizeof(mark));
}

//xval，yval表示该点选择为0（假）还是1（真），该函数表示x的xval选择或者y的yval选择，若x和y相同，1表示x，0表示！x
void add_clause(int x,int xval,int y,int yval){
    x = x*2+xval;
    y = y*2+yval;
    G[x^1].push_back(y); //因为外部中1代表真，0代表假，而mark中时2i代表假，2i+1代表真
    G[y^1].push_back(x);
}

bool solve(){
    for(int i=0;i<n*2;i+=2){
        if(!mark[i]&&!mark[i+1]){//如果两个都没有标记，则搜索
            c = 0;
            if(!dfs(i)){
                while(c>0)mark[S[--c]] = false;//反悔之前标记的结点，然后搜索另一种情况
                if(!dfs(i+1))return false;
            }
        }
    }
    return true;
}
};

twosat solver;

bool isyoung(int aa){
    return aa*n<total;
}

int main(){
    while(scanf("%d%d",&n,&m)==2&&(n||m)){
total = 0;
        solver.init(n);
        for(int i=0;i<n;i++){
            scanf("%d",&age[i]);
            total+=age[i];
        }
        for(int i=0;i<m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            a--;
            b--;
            //if(a==b)continue;
            if(isyoung(age[a])==isyoung(age[b])){
                solver.add_clause(a,0,b,0);//两个都为false
                solver.add_clause(a,1,b,1);//两个都为true
            }
            else solver.add_clause(a,0,b,0);//l两个都为false
        }
        if(solver.solve()){
            for(int i=0;i<n;i++){
                if(!isyoung(age[i])){
                    if(solver.mark[2*i])printf("A\n");
                    else printf("C\n");
                }
                else{
                    if(solver.mark[2*i])printf("B\n");
                    else printf("C\n");
                }
            }
        }
        else printf("No solution.\n");
    }
    return  0;
}