面向对象课程 HW10

前言

本次作业增加了 Message，Group 两个类。 NetWork 中增加了配套的一系列方法。并在原有的关系上增加了 modifyRelation 方法。

第十次作业设计

Message 没什么好说的，按着规格写就可以了。

Group 类涉及到了 ageVar 的查询操作，采取动态维护策略即可。

要提一提的是 modifyRelation 方法。这个方法的作用是更改一对关系的值。如果更改后的值小于等于 0，则删除此对关系。

删除操作对于第九次作业中影响比较大的地方有并查集的维护和三角关系数量的维护。

对于并查集的维护：

朴素的思想是每次删边都重建并查集。但是考虑到每次建立并查集的复杂度为 O(\nlog(n))，每次删边都重建并查集是有很大概率会 t 的。于是我引入了一个 dirty 位。当发生了删边操作时，将 dirty 位置真。当涉及到查询并查集的操作时（即 isCircle 和 queryBlockSum），若 dirty 位为真，则重建并查集，否则直接查询。

对于三角关系的维护：

我的做法是将每一组三元关系保存下来（手写了一个 Tuple 类），当删边操作发生时，遍历所有三元关系，若三元对中包含了删边的两个点，则将此三元关系移除，并将 cntTriple 减一。

伪代码

boolean disjoinSetDirty;        // 脏位

modifyRelation() {
    /*
    ... do sth
    */
    if (/*cond*/) {             // 发生了删边操作
        delCircle();            // 维护三角形边数
        disjoinSetDirty = true; // 维护脏位
        //  do sth
    }
}

isCircle() {
    if (disjoinSetDirty) {
        rebuildDisjointSet();   // 重建并查集
    }
    // do sth
}

queryBlockSum() {
    if (disjoinSetDirty) {
        rebuildDisjointSet();   // 重建并查集
    }
    // do sth
}