O - DAG优化-526互联

#include<bits/stdc++.h>
using namespace std;
struct Node{
    char ch;//下
    vector<char> val;//右
    int left=-1,right=-1;//子节点
}tree[200];
int m=0;
bool flag[200];
string ans[200];
bool finds(int x,char ch){
    for(char k:tree[x].val){
        if(k==ch) return true;
    }
    return false;
}
int build(char ch){
    for(int i=0;i<m;i++){
        if(tree[i].ch==ch || finds(i,ch)) return i;
    }
    tree[m].ch=ch;
    return m++;
}
void build_op(char k,char op,int l,int r){
    for(int i=0;i<m;i++){
        Node x=tree[i];
        if(x.ch==op && x.left==l && x.right==r) {
            tree[i].val.push_back(k);
            return;
        }

    }
    //这里写外面
        tree[m].ch=op;
        tree[m].val.push_back(k);
        tree[m].left=l;
        tree[m].right=r;
        m++;
}
char gets(int x){
    Node k=tree[x];
    if(k.val.size()==0) return k.ch;
    for(char t:k.val){
        if(t=='A'|| t=='B') return t;//优先选a/b的
    }
    return k.val[0];
}
void dfs(int x){
    if(tree[x].left!=-1 && tree[x].right!=-1){
        flag[x]=true;
        dfs(tree[x].left);
        dfs(tree[x].right);
    }
}
void get_ans(char k){
    for(int i=m-1;i>=0;i--){
        if(ans[i][0]==k) {
            dfs(i);
            return;
        }
    }
}
int main(){
    int t;cin>>t;
    for(int i=0;i<t;i++){
        string s;cin>>s;
        int l=build(s[2]),r=build(s[4]);
        build_op(s[0],s[3],l,r);
    }
    for(int i=0;i<m;i++){
        Node x=tree[i];
        if(x.left!=-1 && x.right!=-1) {
            ans[i].push_back(gets(i));
            ans[i].push_back('=');
            ans[i].push_back(gets(x.left));
            ans[i].push_back(x.ch);
            ans[i].push_back(gets(x.right));
        }
    }
    get_ans('A'),get_ans('B');
    for(int i=0;i<m;i++){
        if(flag[i]) cout<<ans[i]<<endl;
    }
}