并查集基础练习

普通并查集

普通并查集有两个优化，这里再记一笔复杂度。

路径压缩，均摊 $O(\log n)$

1	int find(int u) {return fa[u]==u?u:fa[u]=find(fa[u]);}

按秩合并，均摊 $O(\log n)$ ，“秩” 取最大深度或者结点个数

void ut(int u,int v) {
    int fu=find(u),fv=find(v);
    if(sz[fu]>sz[fv]) swap(fu,fv);
    fa[fu]=fv;sz[fv]+=sz[fu];
}

两个都加，均摊 $O(\alpha (n))$ ， $\alpha (n)$ 为反阿克曼函数，增长极慢，可视为常数。

UVA1664 - Conquer a New Region

题意

一个树 $N$ 个点， $N-1$ 条带边权的边，定义两点之间价值为路径上边权的最小值。你雪要找一个中心结点，使它到所有点的价值之和最大化，输出这个最大的价值之和。

$1\le N\le 2\cdot 10^5$

题解

将边权从大到小排序，此时最大的边对答案不会有任何影响，考虑合并两结点。

故用并查集维护已经合并的连通块，并记录当前连通块的答案，记为 $val$ 。考虑如何合并 $u,v$ ，两种情况，中心定在 $u$ 的连通块或中心定在 $v$ 的连通块。因为现在这条边的边权肯定 $\le$ 连通块内的任意边权，故换中心的代价就是 $-val_u+sz_u\cdot w$ ， $u,v$ 取大的即可。

CODE

#include <bits/stdc++.h>
#define int long long 
using namespace std;
typedef long long ll;
const int N = 200010;
struct edge{
    int u,v,w;
    bool operator<(const edge a)const {
        return w>a.w;
    }
}e[N];
int fa[N],n,sz[N];
ll val[N];
int find(int u) {return fa[u]==u?u:fa[u]=find(fa[u]);}
signed main() {
    while(cin>>n) {
        for(int i=1;i<n;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
        for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1,val[i]=0;
        sort(e+1,e+n);
        ll ans=0;
        for(int i=1;i<n;i++) {
            int fu=find(e[i].u),fv=find(e[i].v);
            if(fu!=fv) {
                ll c=max(1ll*sz[fu]*e[i].w+val[fv],1ll*sz[fv]*e[i].w+val[fu]);
                fa[fu]=fv;
                val[fv]=c;
                sz[fv]+=sz[fu];
            }
        }
        printf("%lld\n",val[find(1)]);
    }
}//QAQ ??? 为毛非要define int long long 才能过

可删点并查集

SP5150 - Junk-Mail Filter

SP5150

题意

$N$ 个元素， $M$ 次操作，维护一个并查集，支持两种操作：

M x y：合并 $x$ 和 $y$ 所在的集合
S x：把 $x$ 从所在的集合删除，并独立成为一个新的集合

对于每一组测试数据，输出最后还剩多少个集合

$1\le N\le 10^5 ,1\le M\le 10^6$

题解

这是一个可删点并差集，合并、寻根与普通并查集无异，重在删点。

如果这个点是叶子结点那么直接 $fa_u=u$ 即可，但如果不是，那就会很麻烦，要把它的所有孩子连到它父亲那里。

于是我们干脆不实际删点，而是再开一个新点来表示 $u$ ，而把原来的点当作一个虚点，这只要在开一个数组 $mp_u$ 映射一下 $u$ 当前的实际结点即可。

CODE

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int M = 2000000;
int fa[M],n,m,cs,mp[M],tot,sz[M];
int find(int u) {return fa[u]==u?u:fa[u]=find(fa[u]);}
int main() {
    while(scanf("%d%d",&n,&m)!=EOF) {
        if(n==0&&m==0) break;
        tot=n-1;
        for(int i=0;i<n;i++) fa[i]=i,sz[i]=1,mp[i]=i;
        int ans=n;
        while(m--){ 
            char s[4];int u,v;
            scanf("%s",s);
            if(s[0]=='S') {
                scanf("%d",&u);
                int uu=mp[u];
                int fu=find(uu);
                if(sz[fu]==1) ans--;
                sz[fu]--;
                mp[u]=++tot;
                fa[tot]=tot;sz[tot]=1;
                ans++;
            }else {
                scanf("%d%d",&u,&v);
                int uu=mp[u],vv=mp[v];
                int fu=find(uu),fv=find(vv);
                if(fu!=fv) {
                    fa[fv]=fu;
                    sz[fu]+=sz[fv];
                    ans--;
                }
            }
        }
        printf("Case #%d: %d\n",++cs,ans);

    }
    return 0;
}

HDU6109 - 数据分割

HDU6109

题意

小w来到百度之星的赛场上，准备开始实现一个程序自动分析系统。

这个程序接受一些形如 $x_i=x_j$ 或 $x_i\ne x_j$ 的相等/不等约束条件作为输入，判定是否可以通过给每个 w 赋适当的值，来满足这些条件。

输入包含多组数据。然而粗心的小w不幸地把每组数据之间的分隔符删掉了。他只知道每组数据都是不可满足的，且若把每组数据的最后一个约束条件去掉，则该组数据是可满足的。请帮助他恢复这些分隔符。

题解

使用种类并查集是错的。不等于符号不具有传递性，这里没说 $x_i$ 只有 $0,1$ 两种取值， $x_1\ne x_2,x_2\ne x_3$ 不能取定 $x_1,x_3$ 的关系。

考虑 $x_1\ne x_2$ ， $x_1,x_2$ 所在的集合并能合并，那么维护的并查集上再开一个 vector 存相同的标记，在合并两集合时判断两 vector 有无交集，有交则矛盾。vector 需要启发式合并（小合大），以保证 $O(n\log n)$ 的复杂度。

#include <bits/stdc++.h>
#define _max(x,y) ((x>y)?x:y)
#define _min(x,y) ((x<y)?x:y)
#define SZ(a) ((int)a.size())
using namespace std;
typedef long long ll;
template<typename T>
inline void red(T &x) {
    x=0;bool fg=0;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(T)(ch^48),ch=getchar();
    if(fg) x=-x;
}
template<typename T> bool umax(T &x,T y) {return (x<y)?(x=y,true):(false);}
template<typename T> bool umin(T &x,T y) {return (x>y)?(x=y,true):(false);}
typedef set<int>::iterator si;
const int N = 100010;
int tot,L,T,a[N],fa[N];
vector<int> val[N];
int st[N<<1],top;
void clear() {
    tot=0;
    while(top) fa[st[top]]=st[top],val[st[top]].clear(),top--;
}
int find(int u) {
    return u==fa[u]?u:fa[u]=find(fa[u]);
}
bool check(int a,int b) {
    for(int i=0,j=0;i<SZ(val[a]);i++) {
        while(j<SZ(val[b])&&val[b][j]<val[a][i]) j++;
        if(j<SZ(val[b])&&val[a][i]==val[b][j]) return 0; 
    }
    return 1;
}
void merge(int a,int b) {
    if(SZ(val[a])>SZ(val[b])) swap(a,b);
    fa[a]=b;
    for(int i=0;i<SZ(val[a]);i++) val[b].push_back(val[a][i]); 
    val[a].clear();
    sort(val[b].begin(),val[b].end());
}
int main() {
    scanf("%d",&L);
    for(int i=1;i<=L;i++) fa[i]=i;
    for(int i=1;i<=L;i++){
        int x,y,e;scanf("%d%d%d",&x,&y,&e);
        start:
        st[++top]=x,st[++top]=y;
        bool fail=0;
        if(e) {
            // x=y
            int fx=find(x),fy=find(y);
            if(fx==fy) goto e;
            if(check(fx,fy)) {
                merge(fx,fy);
            } else fail=1;
        }else {
            int fx=find(x),fy=find(y);
            if(fx==fy) fail=1;
            else {
                ++tot;
                val[fx].push_back(tot);
                val[fy].push_back(tot);
            }
        }
        e:
        a[T]++;
        if(fail) {
            T++;
            clear();
        }
    }
    printf("%d\n",T);
    for(int i=0;i<T;i++) printf("%d\n",a[i]);
    return 0;
}

带权并查集

结点带上权值，表示与祖先的相对关系。

HDU3038 - How Many Answers Are Wrong

HDU3038

题意

有一个长度为 $N$ 整数的序列不知具体何值，有 $M$ 个限定，告诉你 $[l_i,r_i]$ 的和为 $w_i$ ，请你判断有多少个限定是与前面矛盾的。（按照顺序来，不引起矛盾的即认为正确，矛盾的忽略）。

$1\le N \le 2\cdot 10^5 ,1\le M \le 4\cdot 10^4$

题解

把序列 $a$ ，前缀和一下转化为 $s$ ，每个限定相当于 $s_{l_i-1} +w=s_{r_i}$ ，虽然不确定 $s_{l_i-1}$ 和 $s_{r_i}$ 的具体值，但是这两数的数量关系十分明确。故可以用并查集将其合并，并带上权值表示其数量关系。

一般的 $fa[u]=v,val[u]=vl$ 就表示 $s_u+vl=s_v$ 。

改写 find(u)，在路径压缩时加上父亲的权值:

int find(int u) {
    if(u==fa[u]) return u;
    int p=fa[u];
    fa[u]=find(fa[u]);
    val[u]+=val[p];
    return fa[u];
}

对于对限制，如果两点在同一连通块中，需要判断两点的 val 差值是否为 $w$ 。
若不在同一连通块中，雪要将其父亲连起来，并改变父亲的权值使 $val[l-1]+w=val[r]$

CODE

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n,m,fa[N],val[N];
int find(int u) {
    if(u==fa[u]) return u;
    int p=fa[u];
    fa[u]=find(fa[u]);
    val[u]+=val[p];
    return fa[u];
}

int main() {
    while(scanf("%d%d",&n,&m)!=EOF) {
        for(int i=0;i<=n;i++) fa[i]=i,val[i]=0;
        int ans=0;
        for(int i=1;i<=m;i++) {
            int l,r,s;scanf("%d%d%d",&l,&r,&s);
            l--;
            int fu=find(l),fv=find(r);
            // val[r]=val[l]+s;
            if(fu!=fv) {
                fa[fu]=fv;
                val[fu]=val[r]-s-val[l];
                // (val[l]+val[fu])+s=val[r]
            }
            else if(val[r]!=val[l]+s) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

POJ1733 - Parity game

POJ1733

题意

长度为 $N$ 的零一序列，不知具体值，现告诉你 $M$ 个限制，形如 $[L,R]$ 的和为奇/偶。让你判断第几个限制之后会出现矛盾。

$1\le N \le 10^9,1\le M\le 5000$

题解

离散化一下，与上一题无异

CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5010;
int fa[N],val[N],b[N<<1],tot,n,QAQ;
struct que{
    int x,y;bool op;
}q[N];
int find(int u) {
    if(u==fa[u]) return u;
    int p=fa[u];
    fa[u]=find(fa[u]);
    val[u]+=val[p];
    return fa[u];
}
int main() {
    scanf("%d%d",&QAQ,&n);
    for(int i=1;i<=n;i++) {
        char s[10];
        scanf("%d%d%s",&q[i].x,&q[i].y,s);
        q[i].x--;
        b[++tot]=q[i].x,b[++tot]=q[i].y;
        q[i].op=(s[0]=='o');
    }
    sort(b+1,b+tot+1);
    tot=unique(b+1,b+tot+1)-b-1;
    for(int i=1;i<=tot;i++) fa[i]=i; 
    for(int i=1;i<=n;i++) {
        q[i].x=lower_bound(b+1,b+tot+1,q[i].x)-b;
        q[i].y=lower_bound(b+1,b+tot+1,q[i].y)-b;
    }
    int ans=n;
    for(int i=1;i<=n;i++) {
        int fx=find(q[i].x),fy=find(q[i].y);
        if(fx==fy) {
            if(((val[q[i].x]-val[q[i].y])&1)!=q[i].op) {
                ans=i-1;
                break;
            }
        }else {
            fa[fx]=fy;
            val[fx]=val[q[i].y]-q[i].op-val[q[i].x];
        }
    }
    printf("%d\n",ans);
    return 0;
}

种类并查集

拆点，一个点分成多点表多种类型，两种类型的话 “敌人的敌人就是朋友”

POJ1417 - True Liars

POJ1417

题意

一个岛上有神与恶魔两个种族，神会说真话，恶魔会说假话。已知神 $p_1$ 个，恶魔 $p_2$ 个，但不知道具体个人是属于哪个。这个人问 $n$ 次，每次的问题为 $x_i,y_i,a$ ，问 $x_i$ ：“ $y_i$ 是否为神？” $a$ 为 yes/no。注意 $x_i,y_i$ 可能为同一个人。输入保证不矛盾。

若最终可得出哪些是神则从小到大输出神的编号，并最终输出end，否则输出no。多组测试数据， $n\le 1000,\;p_1,p_2\le 300$

题解

首先，显然：

$x$ 是神， $y$ 是神 $\mathrm{yes}$
$x$ 是神， $y$ 不是神 $\mathrm{no}$
$x$ 不是神， $y$ 是神 $\mathrm{no}$
$x$ 不是神， $y$ 不是神 $\mathrm{yes}$

所以 $\mathrm{yes}\iff x,y\text{同身份}$ ， $\mathrm{no}\iff x,y\text{不同身份}$ 。

考虑拆点 $x,x'$ 称之为正点和反点，表示两种身份，种类并查集，对于 $\mathrm{yes}$ ：merge(x,y),merge(x',y'),对于 $\mathrm{no}$ ：merge(x',y),merge(x,y')。
最终的图是对称的，我们管一边的就行了。

在同一连通块中的正点之间身份应该一样，反点之间身份应该也一样。假设这个连通块中有 $a$ 个正点 $b$ 个反点，也就是说要么 $a$ 个圣人， $b$ 个恶魔，要么 $b$ 个圣人 $a$ 个恶魔。

凑成圣人个数为 $p_1$ 的方案数唯一才能确定，这个东西跑个dp即可，输出方案只要记录前驱及当前更新的是那个连通块的正/反点。

注意 DP 数组开两维，不能在之前的上面覆盖，会有连通块更新0个圣人，容易出问题，~~只是因为我太菜，调了半天~~

CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int N = 705;
int fa[N<<1],sz[2][N<<1],n,p1,p2,cnt,m;
int dp[N][N],pr[N][N],id[N][N],ty[N][N],tp[N][N];
bool vis[N];
int can[N];
int find(int u) {return u==fa[u]?u:fa[u]=find(fa[u]);}
void ut(int fx,int fy) {
    if(fx==fy) return;
    fa[fy]=fx;
    sz[0][fx]+=sz[0][fy];
    sz[1][fx]+=sz[1][fy];
    cnt++; 
}
void ssolve() {
    int tot=0;
    for(int i=0;i<=m;i++) pr[0][i]=id[0][i]=ty[0][i]=-1,vis[i]=dp[0][i]=0;
    pr[0][0]=0;dp[0][0]=1;
    for(int i=1;i<=m;i++) if(!vis[(find(i)-1)%m+1]) {
        int _id=(find(i)-1)%m+1;
        vis[_id]=1;tot++;
        for(int i=0;i<=p1;i++) pr[tot][i]=id[tot][i]=ty[tot][i]=-1,dp[tot][i]=0;
        for(int j=min(sz[0][_id],sz[1][_id]);j<=p1;j++) {
            if(j-sz[0][_id]>=0&&dp[tot-1][j-sz[0][_id]]!=0) {
                dp[tot][j]+=dp[tot-1][j-sz[0][_id]];
                pr[tot][j]=j-sz[0][_id],id[tot][j]=_id,ty[tot][j]=0;
            }
            if(j-sz[1][_id]>=0&&dp[tot-1][j-sz[1][_id]]!=0) {
                dp[tot][j]+=dp[tot-1][j-sz[1][_id]];
                pr[tot][j]=j-sz[1][_id],id[tot][j]=_id,ty[tot][j]=1;
            }

        }
    }
    if(dp[tot][p1]!=1) printf("no\n");
    else {
        for(int i=0;i<=2*m;i++) can[i]=-1;
        for(int x=p1;x!=0;x=pr[tot][x],tot--) {
            can[id[tot][x]]=ty[tot][x];
        }
        vector<int> ans;
        for(int i=1;i<=2*m;i++) {
            if(can[find(i)]==(i<=m)) ans.push_back((i-1)%m+1); 
        }
        sort(ans.begin(),ans.end());
        for(int i=0;i<ans.size();i++) printf("%d\n",ans[i]);
        printf("end\n");
    }
}
int main() {
    while(cin>>n>>p1>>p2&&n+p1+p2) {
        m=p1+p2;
        for(int i=1;i<=2*m;i++) fa[i]=i,sz[i<=m][i]=1,sz[!(i<=m)][i]=0;
        cnt=0;
        for(int i=1;i<=n;i++) {
            int u,v;char s[5];
            scanf("%d%d%s",&u,&v,s);
            int fu0=find(u),fu1=find(u+m),fv0=find(v),fv1=find(v+m);
            if(s[0]=='n') {
                ut(fu0,fv1);ut(fu1,fv0);
            }else {
                ut(fu0,fv0);ut(fu1,fv1);
            }
        } 
        ssolve();       
    }
}