DFA 最小化_算法

这里是好写的高复杂度写法，外层枚举字符不断分裂节点，mrk 是接受状态，to[u][v] 是颜色为 $u$ 的点指向颜色为 $v$ 的点会分配为什么颜色。

int col[N],n,ch[N][S];
std::map<int,int> to[N];
bool hopcraft() {
    bool ok=false;
    F(c,0,S-1) {
        F(i,1,col[0]) to[i].clear();
        F(u,1,n) {
            int v=ch[u][c]?col[ch[u][c]]:-1;
            if(!to[col[u]][v]) {
                if(!to[col[u]].empty()) to[col[u]][v]=++col[0],ok=true;
                else to[col[u]][v]=col[u];
            }
        } 
        F(u,1,n) {
            int v=ch[u][c]?col[ch[u][c]]:-1;
            col[u]=to[col[u]][v];
        }
    }
    return ok;
}
void work(bool *mrk) {
    F(u,1,n) col[u]=mrk[u];
    col[0]=1;
    while(hopcraft());
}