修复无法完整收集间接从属关系的层级关系精简代码问题

某公司有N名员工，存在M组直接从属关系。若员工3直接/间接受制于员工2，员工2直接/间接受制于员工1，则员工3间接受制于员工1。当某组直接从属关系可转化为间接从属关系时（即存在其他路径连接上级和下属），可移除该直接关系；若移除后从属关系完全消失则不可移除。需尽可能多地移除符合条件的直接关系，最终返回剩余直接关系的数量。

输入格式 #

• 第一行：两个整数N（员工数）和M（直接关系数）
• 后续M行：每行两个整数a和b，表示b直接隶属于a

示例测试用例 #

输入 #

5 8
3 5
1 4
4 3
1 3
4 5
1 2
1 5
2 3

输出 #

5

解释 #

可移除的直接关系包括：

• 1→3（存在路径1→2→3）
• 1→5（存在路径1→2→3→5）
• 4→5（存在路径4→3→5）
  移除后剩余5组直接关系。

你的代码核心缺陷是仅在添加单个直接关系时一次性推导间接关系，无法处理后续新增关系带来的连锁更新。例如：

1. 当你先添加1→3，此时1的indirect集合为空；
2. 后续添加1→2、2→3时，代码不会回溯更新1的indirect集合，导致1的indirect中没有3；
3. 最终无法识别1→3是可移除的直接关系。

这种方式只能捕获添加关系时当下存在的间接路径，完全遗漏了后续关系建立后产生的新间接路径。

#include <fstream>
#include <set>
#include <map>
#include <queue>
using namespace std;

struct relationship {
    set<int> direct;   // 直接下属
    set<int> indirect; // 所有间接下属（通过路径可达的非直接下属）
};

// 检查元素是否在集合中，使用set的find方法更高效
bool isInSet(const set<int>& s, int val) {
    return s.find(val) != s.end();
}

// 计算节点node的所有间接下属：通过BFS遍历所有可达的下属节点
void calculateIndirectSubordinates(map<int, relationship>& rels, int node) {
    queue<int> q;
    set<int> visited;

    // 初始化队列：将所有直接下属加入，作为BFS起点
    for (int sub : rels[node].direct) {
        q.push(sub);
        visited.insert(sub);
    }

    while (!q.empty()) {
        int current = q.front();
        q.pop();

        // 遍历current的直接下属，这些都是node的间接下属
        for (int sub : rels[current].direct) {
            if (!isInSet(visited, sub)) {
                visited.insert(sub);
                rels[node].indirect.insert(sub);
                q.push(sub);
            }
        }
    }
}

int main() {
    ifstream fi("input.inp");
    ofstream fo("output.out");
    map<int, relationship> relationships;
    int n, m, a, b;

    fi >> n >> m;

    // 第一步：先收集所有直接从属关系
    for (int i = 0; i < m; ++i) {
        fi >> a >> b;
        relationships[a].direct.insert(b);
    }

    // 第二步：为每个节点计算所有间接下属
    for (int i = 1; i <= n; ++i) {
        calculateIndirectSubordinates(relationships, i);
    }

    // 第三步：统计可移除的直接关系数量
    int removableCount = 0;
    for (int i = 1; i <= n; ++i) {
        for (int sub : relationships[i].direct) {
            // 如果该直接下属同时是间接下属，说明存在其他路径，可移除
            if (isInSet(relationships[i].indirect, sub)) {
                removableCount++;
            }
        }
    }

    // 剩余关系数 = 原关系数 - 可移除数量
    fo << m - removableCount << endl;

    fi.close();
    fo.close();
    return 0;
}

1. 分阶段处理：先完整收集所有直接关系，再统一计算间接从属关系，避免动态添加时的遗漏。
2. BFS遍历获取全量可达性：对每个节点使用广度优先搜索，遍历所有通过路径可达的下属节点，确保不遗漏任何间接从属关系，无论关系添加顺序如何。
3. 高效集合查询：使用set::find替代手动遍历集合，大幅提升查询效率。
4. 准确统计可移除关系：遍历所有直接关系，若直接下属存在于间接从属集合中，说明存在替代路径，该直接关系可安全移除。

内容的提问来源于stack exchange，提问作者Minh Tuấn Nguyễn