新学到的边双科技

Joker_Fish

2024-09-27 14:51:57

Algo. & Theory

出处:模拟赛(模拟赛题目要求动态加边动态查询两点是否在同一个边双内)。

板题 AC 记录。

先说优缺点:

优点:在可以离线的情况下可以支持动态加边以及快速查询两个点是否在同一个边双。复杂度同为 O(n) 且常数比 tarjan 小一些(我的 tarjan 记录)。

缺点:不好扩展到点双和强联通分量。

先讲做法:随便搞出图的一个生成树然后对其进行 dfs 确定每个节点的父亲和深度。之后对于每条边,我们标记树上两点之间的全部边。对于一个查询(询问两点之间是否在同一个边双)只要两点之间的边全部被标记了两次及以上那么就在一个边双里,否则不在。

这个做法的正确性显然,但是复杂度是 O(n^2) 的,需要优化。

发现我们只是要标记路径和查询路径标记次数的最小值,考虑树剖。但是这是 O(n\log ^2 n) 的(你也可以考虑用 LCT 等科技优化到 O(n\log n)),还是不够快且常数过屎,仍需优化。

发现我们浪费了一些东西,比如一条边被标记两次之后就不需要继续标记了,考虑用并查集来维护边双关系。在暴力上跳的时候同时记录边的标记次数,达到 2 之后就 merge 两个点。同时在上跳的时候我们可以直接跳过其他标记次数达到 2 的边直接到达所在边双中深度最低的节点的父亲。查询直接并查集判断两个点是否在同一个边双。

并查集 O(1),总复杂度由于每条边只会访问 2 次所以是 O(n) 的。

#include<bits/stdc++.h>
#define int long long
//#define endl '\n'
using namespace std;
const int mod=998244353,inf=0x3f3f3f3f3f3f3f3f;
int u[2000010],v[2000010];
struct DSU{
    int fa[800010];
    int find(int x)
    {
        if(fa[x]==x)return x;
        return fa[x]=find(fa[x]);
    }
    int merge(int u,int v)
    {
        u=find(u),v=find(v);
        if(u==v)return 0;
        fa[u]=v;
        return 1;
    }
    void init()
    {
        for ( int i = 1 ; i <= 8e5 ; i++ )
        {
            fa[i]=i;
        }
    }
}dsu;
int n,m;
vector<int>e[800010];
void add(int u,int v){if(dsu.merge(u,v))e[u].push_back(v),e[v].push_back(u);}
int fa[800010],dep[800010],cnt[800010];
void dfs(int x,int f)
{
    fa[x]=f;
    dep[x]=dep[f]+1;
    for ( auto v:e[x] )
    {
        if(v==f)continue;
        dfs(v,x);
    }
}
void merge(int u,int v)
{
    u=dsu.find(u),v=dsu.find(v);
    while(u!=v)
    {
        if(dep[u]<dep[v])swap(u,v);
        cnt[u]++;
        if(cnt[u]==2)dsu.merge(u,fa[u]);
        u=fa[u];
        u=dsu.find(u);
    }
}
vector<int>vec[500010];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >>n >> m;
    for ( int i = 1 ; i <= m ; i++ )cin >> u[i] >>v[i];
    dsu.init();
    for ( int i = 1 ; i <= m ; i++ )add(u[i],v[i]);
    dsu.init();
    for ( int i = 1 ; i <= n ; i++ )if(!dep[i])dfs(i,i);
    for ( int i = 1 ; i <= m ; i++ )merge(u[i],v[i]);
    for ( int i = 1 ; i <= n ; i++ )vec[dsu.find(i)].push_back(i);
    int cnt=0;
    for ( int i = 1 ; i <= n ; i++ )if(vec[i].size())cnt++;
    cout << cnt << endl;
    for ( int i = 1 ; i <= n ; i++ )
    {
        if(vec[i].size())
        {
            cout << vec[i].size() << " ";
            for ( auto j:vec[i] )cout << j << " ";
            cout << endl;
        }
    }
    return 0;
}

接下来讲动态加边动态求边双怎么做,其实就是把生成树生成方案改成早加的边优先即可。加边的时候就标记,查询的时候就查询,依次进行即可。