22牛客多校1 J.Serval and Essay (启发式合并)

传送门

大致题意 : 一个n个点m条边的无重边无自环的有向图, 初始均为白点, 若某个点的前驱节点均为黑点, 则该点可以被染黑, 初始可任意染黑一点, 求最大化图中黑点的数量

思路 : 首先可以画一张图, 如样例, 起始我们染黑1, 后续2, 3可被染黑, 不难发现, 1,2,3可以互相影响, 染黑3 不如 染黑2, 染黑2 不如 染黑 1, 这时我们可以将这三个点看做一个点, 即进行合并, 可以发现合并后并不会对原图产生影响, 如节点 5 在合并和 由{1, 2, 3} 和 {4} 控制并不能染黑, 若有另一点能到{1, 2, 3}, 则{1, 2, 3}并不能合并, 可知合并后的{1, 2, 3}的前后节点不受影响, 即当前合并后的节点集合的节点数即为最大, 若有多个集合取极大值即可

显然暴力是会超时的, 因为会遍历到所有重边来进行合并, 这里可以想到用启发式合并来进行操作, 对于两个可以连接的集合, 我们只遍历出边数小的那个集合, 将它与出边大的合并, 来优化时间复杂度, 最坏情况下m条边, 分为m/2, m/2两个集合, 每次只遍历一个, 不断向下合并, 复杂度为 O(m/2 * log m), 再加上需要用到set操作, 总时间复杂度为O(m/2 * log m * log m), 是可以做的

代码如下: 

#include <bits/stdc++.h>

using namespace std;

stringstream ss;
#define endl "\n"
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2e5+10, M = 30, mod = 1e9+7;
const int INF = 0x3f3f3f3f;

int n;
int p[N], sz[N]; // p为并查集集合, sz为集合大小
set<int> pre[N], ne[N]; // 分别记录前驱节点和后缀节点

int find(int x) 
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void merge(int x, int y) // 启发式合并
{
    x = find(x), y = find(y);
    if(x == y) return;
    if(ne[x].size() < ne[y].size()) swap(x, y); // 保证x是出边大的那个
    p[y] = x, sz[x] += sz[y]; // 将y向x合并
    vector<PII> seg; // 合并一边x,y后, 对于{x, y}和其他点 可能还能继续合并, 用seg保存起来, dfs合并
    for(auto t : ne[y])
    {
        pre[t].insert(x), ne[x].insert(t), pre[t].erase(y); // 合并操作
        if(pre[t].size() == 1) seg.push_back({t, x});
    }
    for(auto t : seg) merge(t.first, t.second); // 继续合并
}

void solve(int t)
{
    cin>>n;
    for(int i = 1; i<=n; i++) p[i] = i, sz[i] = 1, pre[i].clear(), ne[i].clear();

    for(int i = 1; i<=n; i++)
    {
        int k;
        cin>>k;
        for(int j = 1; j<=k; j++)
        {
            int x;
            cin>>x;
            ne[x].insert(i);
            pre[i].insert(x);
        }
    }
    for(int i = 1; i<=n; i++)
    {
        if(pre[i].size() == 1) merge(*pre[i].begin(), i); // 对入边为1的点与当前点进行合并
    }
    int res = 0;
    for(int i = 1; i<=n; i++) res = max(res, sz[i]);
    cout<<"Case #"<<t<<": "<<res<<endl;
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//    solve();
    int T;
    cin>>T;
    for(int i = 1; i<=T; i++)
    {
        solve(i);
    }
}