DAG优化

大家都学过了代码优化，其中有一个DAG优化，这次我们就练习这个操作。

Input 输入第一行为一个整数ｎ(n < 100)，表示该组输入的表达式的个数

之后ｎ行为表达式，每个变量为一个字母，表达式仅包括二元运算 + - * /

例如：A=B+C

Output 通过构造DAG图，进行代码优化，只需要保留AB，删除无用变量，删除变量时，尽量保留最早出现的变量。

PS:保证AB的值不同

Sample Input

3 A=B+C B=B+B A=C+C

Sample Output

B=B+B A=C+C #include <bits/stdc++.h> using namespace std; int n; int cnt; struct Node { char id; int left = -1, right = -1; vector<char> var; } node[110]; bool find_var(int i,char c) { for(char j : node[i].var)if(j == c)return 1; return 0; } int add_node(char c) { for(int i = cnt-1; i >= 0; --i) if(node[i].id == c || find_var(i,c))return i; node[cnt].id = c; return cnt++; } void add_operator(char c,char op,int l,int r) { for(int i = cnt-1; i >= 0; --i) if(node[i].left == l && node[i].right == r && node[i].id == op) { node[i].var.push_back(c); return ; } node[cnt].id = op; node[cnt].var.push_back(c); node[cnt].left = l; node[cnt].right = r; cnt++; } char s[10]; char ans[110][10]; bool flag[110]; void dfs(int x) { if(node[x].left != -1) { flag[x] = 1; dfs(node[x].left); dfs(node[x].right); } } int main() { cnt = 0; scanf("%d",&n); for(int i = 0; i < n; ++i) { scanf("%s",s); int l = add_node(s[2]); int r = add_node(s[4]); add_operator(s[0],s[3],l,r); } for(int i = 0; i < cnt; ++i) { if(node[i].left != -1) { ans[i][0] = node[i].var[0]; ans[i][1] = '='; Node ll = node[node[i].left],rr = node[node[i].right]; ans[i][2] = ll.var.size() > 0 ? ll.var[0] : ll.id; ans[i][3] = node[i].id; ans[i][4] = rr.var.size() > 0 ? rr.var[0] : rr.id; ans[i][5] = 0; } } for(int i = cnt-1; i >= 0; --i) { if(ans[i][0] == 'A') { dfs(i); break; } } for(int i = cnt-1; i >= 0; --i) { if(ans[i][0] == 'B') { dfs(i); break; } } for(int i = 0; i < cnt; ++i)if(flag[i])puts(ans[i]); return 0; }