贪心构造+枚举子集+有向图判环

lc3445

无向图当中用一个数组标记每个节点是否访问过，记录这个节点它的父节点，如果一个节点不是fa ＆＆被访问过，就说明环

可以bfs/dfs/union判环

推到有向图 两种状态表示已经无法判定，我们可以用到三色染色法

class Solution {

public:
vector<vector<int>> supersequences(vector<string>& words) {
// 收集有哪些字母，同时建图
int all = 0, mask2 = 0;
vector<int> g[26]{};
for (auto& s : words) {
int x = s[0] - 'a', y = s[1] - 'a';
all |= 1 << x | 1 << y;
if (x == y) {
mask2 |= 1 << x;
}
g[x].push_back(y);
}

// 判断是否有环
auto has_cycle = [&](int sub) -> bool {
int color[26]{};
auto dfs = [&](this auto&& dfs, int x) -> bool {
color[x] = 1;
for (int y : g[x]) {
// 只遍历在 sub 中的字母
if ((sub >> y & 1) == 0) {
continue;
}
if (color[y] == 1 || color[y] == 0 && dfs(y)) {
return true;
}
}
color[x] = 2;
return false;
};
for (int i = 0; i < 26; i++) {
// 只遍历在 sub 中的字母
if (color[i] == 0 && sub >> i & 1 && dfs(i)) {
return true;
}
}
return false;
};

unordered_set<int> st;
int max_size = 0;
// 枚举 mask1 的所有子集 sub
int mask1 = all ^ mask2;
int sub = mask1;
do {
int size = popcount((unsigned) sub);
// 剪枝：如果 size < min_size 就不需要判断了
if (size >= max_size && !has_cycle(sub)) {
if (size > max_size) {
max_size = size;
st.clear();
}
st.insert(sub);
}
sub = (sub - 1) & mask1;
} while (sub != mask1);

vector<vector<int>> ans;
for (int sub : st) {
vector<int> cnt(26);
for (int i = 0; i < 26; i++) {
cnt[i] = (all >> i & 1) + ((all ^ sub) >> i & 1);
}
ans.push_back(cnt);
}
return ans;
}
};