并查集

Exclusive-OR

 UVALive - 4487 

 带权并查集，回去再写

#include <bits/stdc++.h>
using namespace std;
#define CLR(m,a) memset(m,a,sizeof(m))
const int maxn=20010;
int f[maxn],d[maxn];
int n,q;
void init(){
    for(int i=0;i<=n;i++){
        f[i]=i;
        d[i]=0;
    }
}

int gf(int x){
    if(x!=f[x]){
        int r=f[x];
        f[x]=gf(r);
        d[x]=d[x]^d[r];
    }
    return f[x];
}
int uni(int a,int b,int v){
    int pa=gf(a);
    int pb=gf(b);
    if(pa==pb) return (d[a]^d[b])==v;
    if(pa==n) swap(pa,pb);
    f[pa]=pb;
    d[pa]=d[a]^d[b]^v;
    return 1;
}

struct Ask{
    int p,a;
    bool operator<(const Ask& x){
        return p<x.p;
    }
};
Ask ask[maxn<<1];
int query(int k){
    for(int i=0;i<k;i++) ask[i].p=gf(ask[i].a);
    sort(ask,ask+k);
    int l=0,ans=0;
    while(l<k){
        int r=l;
        while(r+1<k&&ask[r].p==ask[r+1].p) r++;
        int num=r-l+1;
        if(ask[l].p!=n&&num&1) return -1;
        for(int i=l;i<=r;i++) ans^=d[ask[i].a];
        l=r+1;
    }
    return ans;
}
int main()
{
    int kase=0;
    char c[5],s[20];
    while(scanf("%d%d",&n,&q)&&(n||q)){
        printf("Case %d:
",++kase);
        int flag=-1;
        init();
        int ct=0;
        for(int u=0;u<q;u++){
            scanf("%s",c);
            if(c[0]=='I'){
                ct++;
                gets(s);
                if(flag!=-1) continue;
                int p,q,v;
                int res;
                int t=sscanf(s,"%d%d%d",&p,&q,&v);
                if(t==2){
                    res=uni(p,n,q);
                }else{
                    res=uni(p,q,v);
                }
                if(!res) flag=ct;
            }else {
                int k;
                scanf("%d",&k);
                for(int i=0;i<k;i++) {
                    scanf("%d",&ask[i].a);
                }
                if(flag!=-1) continue;
                int res=query(k);
                if(res==-1) puts("I don't know.");
                else printf("%d
",res);
            }
        }
        if(flag!=-1) printf("The first %d facts are conflicting.
",flag);
        puts("");
    }
    return 0;
}

Almost Union-Find

 UVA - 11987

题意：要求实现带删除的并查集。

思路就是将要点的影响力减为0。然后开辟新的节点（代码中的id[i]就是这个用处）去合并。

#include <bits/stdc++.h>
using namespace std;
#define CLR(m,a) memset(m,a,sizeof(m))

const int maxn=200010;

int f[maxn],cnt[maxn],sum[maxn];
int id[maxn]; //本替关键
int n,m;
int tot;
void init(){
    for(int i=0;i<=n;i++){
        f[i]=i;
        sum[i]=i;
        cnt[i]=1;
        id[i]=i;
    }
}

int gf(int x){
    return x==f[x]?f[x]:f[x]=gf(f[x]);
}

void uni(int a,int b){
    int pa=gf(a);
    int pb=gf(b);
    if(pa!=pb){
        f[pa]=pb;
        cnt[pb]+=cnt[pa];
        sum[pb]+=sum[pa];
    }
}

void move(int a){
    int pa=gf(id[a]);  //
    sum[pa]-=a;
    cnt[pa]--;
    //开辟新的节点
    id[a]=++tot;
    f[tot]=tot;
    sum[tot]=a;
    cnt[tot]=1;
}

int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        init();
        int c,p,q;
        tot=n;
        for(int i=0;i<m;i++){
            scanf("%d",&c);
            if(c==3){
                scanf("%d",&p);
                int pf=gf(id[p]);
                printf("%d %d
",cnt[pf],sum[pf]);
            }else{
                scanf("%d%d",&p,&q);
                if(c==1){
                    uni(id[p],id[q]);
                }else{
                    int pf=gf(id[p]),qf=gf(id[q]);
                    if(pf==qf) continue;
                    move(p);
                    uni(id[p],id[q]);
                }
            }
        }
    }
    return 0;
}

Junk-Mail Filter

HDU - 2473

题意：并查集的删除．

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
int vis[maxn];
int f[maxn],b[maxn];
int cnt=0;
int gf(int x){
    return x==f[x]?x:f[x]=gf(f[x]);
}

int main(){
    int n,m;
  //  freopen("in.txt","r",stdin);
    int kase=0;
    while(scanf("%d%d",&n,&m)&&(n||m)){
    char s[4];
    int x,y;
    cnt=n;
    memset(vis,0,sizeof(vis));
    for(int i=0;i<=n;i++) {
        f[i]=i;
        b[i]=i;
    }
    for(int i=0;i<m;i++){
        scanf("%s",s);
        if(s[0]=='S'){
            scanf("%d",&x);
            b[x]=cnt;
            f[cnt]=cnt++;
        }else{
            scanf("%d%d",&x,&y);
            int pa=gf(b[x]),pb=gf(b[y]);
            if(pa!=pb) f[pa]=pb;
        }
    }
    int ans=0;
    for(int i=0;i<n;i++){
        int r=gf(b[i]);
        if(!vis[r]){
            ans++;
            vis[r]=1;
        }
    }
    printf("Case #%d: %d
",++kase,ans);
    }
}

Warfare

HDU - 2904

题意：给ｎ个点，点权为w，相连的边的权值为点权值之和．现在要破坏一些边使得图中不存在环，问最小代价是多少（代价即为破坏边的权值）

比较水～给边排序一下，然后并查集搞

#include <bits/stdc++.h>
using namespace std;
const int maxn=110;

int f[maxn];
struct Edge{
    int u,v,w;
    bool operator <(const Edge& a)const{
        return w>a.w;
    }
}e[maxn*maxn];
int w[maxn],g[maxn][maxn];

int gf(int x){
    return x==f[x]?x:f[x]=gf(f[x]);
}

int main(){
    int t;
//    freopen("in.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        int n;
        memset(g,0,sizeof(g));
        scanf("%d",&n);
        int u,v,m;
        for(int i=0;i<n;i++){
            scanf("%d%d%d",&u,&w[i],&m);
            for(int j=0;j<m;j++){
                scanf("%d",&v);
                g[u][v]=g[v][u]=1;
            }
        }
        int cnt=0;
        int sum=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(g[i][j]){
                    e[cnt].u=i;
                    e[cnt].v=j;
                    e[cnt].w=w[i]+w[j];
                    sum+=e[cnt].w;
                    cnt++;
                }
            }
        }
        sort(e,e+cnt);
        for(int i=0;i<n;i++) f[i]=i;
        int temp=0;
        for(int i=0;i<cnt;i++){
            int pa=gf(e[i].u);
            int pb=gf(e[i].v);
            if(pa!=pb){
                f[pa]=pb;
                temp+=e[i].w;
            }
        }
        printf("%d
",sum-temp);
    }
    return 0;
}