J. Serval and Essay

题解

考虑通过“x确定y”这种关系将x和y进行合并，因为如果确定了x就能确定y，那么贪心地想肯定是确定x能得到更大的答案，那么就没有必要再去考虑从y出发了，所有从y连出去的边改成从x连出去。

当“x to y”这条边被合并之后，原本由y指向的点就变成了由x指向，在不断合并的过程中，如果从x出发最终能在t汇聚，那么最后一定会使得t仅由x指向（因为会合并出很多个“x to t”的边，如果维护集合的话就可以自动去重），即出现了“x决定t”，这个时候就需要继续合并。

合并的总次数显然是$O(n)O(n)$的，由于合并的是两个点连出去的点的集合，所以考虑启发式合并，复杂度约为$O(n{}^{2}n+k\log n)O(n\backslash log^2n+k\backslash log\; n)$。

set<int>to[N], from[N];
int fa[N], sz[N];
int findf(int x) {
    if (fa[x] == x)return x;
    return fa[x] = findf(fa[x]);
}
void _Merge(int x, int y) {
    x = findf(x), y = findf(y);
    if (x == y)return;
    if (to[x].size() < to[y].size())
        swap(x, y);
    fa[y] = x;
    sz[x] += sz[y];
    vector<pair<int, int> >mg;
    for (auto t : to[y]) {
        to[x].insert(t);
        from[t].erase(y);
        from[t].insert(x);
        if (from[t].size() == 1)
            mg.push_back(make_pair(t, x));
    }
    for (auto [x, y] : mg)
        _Merge(x, y);
}

int main() {
    int T = fast_IO::read();
    for (int ti = 1; ti <= T; ++ti) {
        int n = fast_IO::read();
        for (int i = 1; i <= n; ++i)fa[i] = i, sz[i] = 1;
        for (int i = 1; i <= n; ++i) {
            int k = fast_IO::read();
            for (int j = 1; j <= k; ++j) {
                int y = fast_IO::read();
                to[y].insert(i);
                from[i].insert(y);
            }
        }
        for (int i = 1; i <= n; ++i)
            if (from[i].size() == 1)
                _Merge(*from[i].begin(), i);
        int ans = 0;
        for (int i = 1; i <= n; ++i)
            ans = max(ans, sz[i]);
        printf("Case #%d: %d\n", ti, ans);
        for (int i = 1; i <= n; ++i)
            to[i].clear(), from[i].clear();
    }
    return 0;
}