[UVA] 1391 - Astronauts

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
#define N 100005
vector<int> s[N*2];
int mark[N*2];
struct TwoSAT{
    int n;
    stack<int> _stack;
    int dfs(int x){
        if(mark[x^1]) return 0;
        if(mark[x]) return 1;
        mark[x]=1;
        _stack.push(x);
        int i;
        for(i=0;i<s[x].size();i++){
            int v=s[x][i];
            if(!dfs(v)) return 0;
        }
        return 1;
    }
    void init(int n){
        this->n=n;
        int i;
        for(i=0;i<n*2;i++)
            s[i].clear();
        memset(mark,0,sizeof(mark));
    }
    void add(int x,int a,int y,int b){
        x=x*2+a;
        y=y*2+b;
        s[x^1].push_back(y);
        s[y^1].push_back(x);
    }
    int solve(){
        int i;
        for(i=0;i<n*2;i+=2){
            if(!mark[i] && !mark[i+1]){
                if(!dfs(i)){
                    while(_stack.size()){
                        int x=_stack.top();
                        _stack.pop();
                        mark[x]=0;
                    }
                    if(!dfs(i+1)) return 0;
                }
            }
        }
        return 1;
    }
}_TwoSAT;
int age[N],type[N];
int main(){
    int n,m,x,y,a,b,i,j,all;
    while(scanf("%d%d",&n,&m)!=EOF && n+m){
        _TwoSAT.init(n);
        all=0;
        for(i=0;i<n;i++){
            scanf("%d",&age[i]);
            all+=age[i];
        }
        for(i=0;i<n;i++)
            if(age[i]*n>=all) type[i]=1;
            else type[i]=0;
        for(i=0;i<m;i++){
            scanf("%d%d",&x,&y);
            x--,y--;
            _TwoSAT.add(x,1,y,1);
            if(type[x]==type[y])
                _TwoSAT.add(x,0,y,0);
        }
        if(!_TwoSAT.solve()) puts("No solution.");
        else{
            for(i=0;i<n;i++){
                if(mark[i*2+1]==0) puts("C");
                else{
                    if(type[i]) puts("A");
                    else puts("B");
                }
            }
        }
    }
}