AC

题目描述
在设计关系数据库的表格时，术语“函数依赖”（FD）被用来表示不同域之间的关系。函数依赖是描述一个集合中的域的值与另一个集合中的域的值之间的关系。记号 X→Y 被用来表示当集合 X 中的域被赋值后，集合 Y 的域就可以确定相应的值。例如，一个数据表格包含“社会治安编号”（S）、“姓名”（N）、“地址”（A）、“电话”（P）的域，并且每个人都与某个特定的互不相同的 S 值相对应，根据域 S 就可以确定域 N 、 A 、 P 的值。这就记作 S→{N,A,P}。

写一个程序以找出一组依赖中所有的冗余依赖。一个依赖是冗余的是指它可以通过组里的其他依赖得到。例如，如果组里包括依赖 A→B 、 B→C 和 A→C，那么第三个依赖是冗余的，因为域 C 可以用前两个依赖得到（域 A 确定了域 B 的值，同样域 B 确定了域 C 的值）。在 A→B 、 B→C 、 C→A 、 A→C 、 C→B 和 B→A 中，所有的依赖都是冗余的。

现在要求你编写一个程序，从给定的依赖关系中找出冗余的。

输入格式
第一行是一个不超过 100 的整数 n，它表示文件中函数依赖的个数。

从第二行起每一行是一个函数依赖且互不重复，每行包含用字符 - 和 > 隔开的非空域列表。列表月包含大写的字母，函数依赖的数据行中不包括空格和制表符，不会出现“平凡”冗余依赖（如 A→A）。虽然文件中没有对函数依赖编号，但其顺序就是编号 1 到 n。

输出格式
每一行输出一个冗余依赖，以及其他依赖的一个序列以说明该依赖是冗余的。格式为 FD x is redundant using FDs: p
1
​
p
2
​
⋯p
k
​
。其中 x 是冗余的依赖的编号，p
1
​
,p
2
​
,⋯,p
k
​
是用来证明 x 是冗余依赖的依赖序列。

如果许多函数依赖的序列都能被用来说明一个依赖是冗余的，则输出其中最短的证明序列。

如果这些函数依赖中不包含冗余依赖，则输出 No redundant FDs。

题解：
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
using namespace std;

const int MAXN = 105;
// 每条依赖：左部、右部，26个字母bit标记
bool L[MAXN][26], R[MAXN][26];
int n;

// 判断 a集合 是否包含 b集合
bool contain(bool *a, bool *b) {
for (int i = 0; i < 26; ++i)
if (b[i] && !a[i]) return false;
return true;
}

// 集合合并：dst = dst | src
void unite(bool *dst, bool *src) {
for (int i = 0; i < 26; ++i)
dst[i] |= src[i];
}

struct State {
bool set[26];
vector<int> path; // 使用的依赖编号(原始1开始)
};

// 检查第del号依赖是否冗余，返回最短路径；空vector表示不冗余
vector<int> check(int del) {
State start;
memset(start.set, 0, sizeof(start.set));
start.path.clear();
// 初始集合 = 待检查依赖左部
memcpy(start.set, L[del], sizeof(start.set));

bool vis[1<<26] = {false}; // 2^26太大，改用数组标记26字母状态访问
// 改用二维bool标记某个字母集合是否访问过
bool visited[1000][26] = {false};
queue<State> q;
q.push(start);
memcpy(visited[0], start.set, sizeof(visited[0]));

while (!q.empty()) {
    State cur = q.front();
    q.pop();
    // 已经推导出右部，找到最短路径
    if (contain(cur.set, R[del])) {
        return cur.path;
    }
    // 枚举所有可用依赖，跳过del自身
    for (int i = 0; i < n; ++i) {
        if (i == del) continue;
        // 当前集合包含这条依赖左部，才能使用
        if (!contain(cur.set, L[i])) continue;
        State nxt = cur;
        unite(nxt.set, R[i]);
        nxt.path.push_back(i+1); // 编号从1开始
        // 判重：该字母集合是否走过
        bool same = false;
        for (int t = 0; t < 1000; t++) {
            bool eq = true;
            for (int c = 0; c < 26; c++) {
                if (nxt.set[c] != visited[t][c]) {eq=false;break;}
            }
            if (eq) {same=true;break;}
        }
        if (same) continue;
        // 存入访问标记
        for (int t=0;t<1000;t++) {
            bool empty=true;
            for(int c=0;c<26;c++) if(visited[t][c]) empty=false;
            if(empty) {
                memcpy(visited[t], nxt.set, sizeof(visited[t]));
                break;
            }
        }
        q.push(nxt);
    }
}
return {};

}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
string s;
for (int i = 0; i < n; i) {
cin >> s;
memset(L[i],0,sizeof(L[i]));
memset(R[i],0,sizeof(R[i]));
int pos = s.find("->");
// 解析左部
for (int j=0;j<pos;j) L[i][s[j]-'A']=true;
// 解析右部
for (int j=pos+2;j<s.size();j++) R[i][s[j]-'A']=true;
}

bool has_red = false;
for (int k=0;k<n;k++) {
    vector<int> res_path = check(k);
    if (!res_path.empty()) {
        has_red = true;
        cout << "FD " << k+1 << " is redundant using FDs:";
        for (int x : res_path) cout << " " << x;
        cout << "\n";
    }
}
if (!has_red) {
    cout << "No redundant FDs.\n";
}
return 0;

}