并查集

种类并查集
HDU3038
把和转换为差

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 200010;
int p[maxn],r[maxn];
int n,m,u,v,l,rc,cnt,k;
void init(){
    memset(r,0,sizeof r);
    memset(p,-1,sizeof p);
    cnt = 0;
}
int find(int x){
    if(p[x]==-1) return x;
    int t = find(p[x]);
    r[x]+=r[p[x]];
    return p[x]=t;
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        init();
        for(int i = 0; i < m; i++){
            scanf("%d%d%d",&u,&v,&k);
            if(u>v) swap(u,v);
            u-=1;
            int t1 = find(u), t2 = find(v);
            if(t1!=t2){
                p[t2]=t1;
                r[t2]=r[u]-r[v]+k;
            }
            else{
                if(r[v]-r[u]!=k) cnt++;
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

扩展并查集
POJ1192

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
const int maxn = 150003;
int p[maxn],rank[maxn];
using namespace std;
void init(){
    for(int i = 0; i < maxn; i++) p[i] = i;
    memset(rank,0,sizeof rank);
}
int find(int x){
    return p[x]==x?x:find(p[x]);
}
bool same(int x,int y){
    return find(x)==find(y);
}
bool link(int x,int y){
    x = find(x); y = find(y);
    if(x==y) return false;
    if(rank[x]<rank[y])
        p[x] = y;
    else{
        p[y] = x;
        if(rank[x]==rank[y])
            rank[x]++;
    }
}
int main(){
    int num,n,k,a,b,fake=0;
    scanf("%d%d",&n,&k);
    init();
    for(int i = 0; i < k; i++){
        scanf("%d%d%d",&num,&a,&b);
        if(a>n||b>n)
            fake++;
        else if(num==1){
            if(same(a,b+n)||same(a,b+2*n))
                fake++;
            else{
                link(a,b);
                link(a+n,b+n);
                link(a+2*n,b+2*n);
            }
        }
        else{
            if(same(a,b+2*n)||same(a,b))//....
                fake++;
            else{
                link(a,b+n);
                link(a+n,b+2*n);
                link(a+2*n,b);
            } 
        }
    }
    printf("%d\n",fake);
    return 0;
}

马甲并查集
HDU2473
写的不是很好 1000+ms
实测秩优化没啥卵用

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
const int maxn = 3e6;
int p[maxn];
int maxx,n,m,a,b,cnt,pi,kase;
char str[5]; 
void init(){ 
    for(int i = 0; i < n ; i++){
        p[i]=i+n;//确保父亲都是马甲 
    }
    for(int i = n; i < maxn; i++){
        p[i]=i;
    }
//    memset(used,0,sizeof used);
    maxx=2*n;
    cnt=0;
}
int find(int x){
    return p[x]==x?p[x]:p[x]=find(p[x]);
}
void link(int a,int b){
    a=find(a);b=find(b);
    if(a!=b) p[b]=a;
}
int main(){
    while(scanf("%d%d",&n,&m),n){
        init(); 
        for(int i = 0; i < m; i++){
            scanf("%s",str);
            if(str[0]=='M'){
                scanf("%d%d",&a,&b);
                a=find(a);b=find(b);
                if(a!=b){
                    link(a,b);
                }
            }
            else{
                scanf("%d",&a);
                p[a]=maxx++;
            }
        }
        map<int,int> used;
        for(int i = 0; i < n; i++){
            pi=find(i);
            if(!used[pi]){
                cnt++;
                used[pi]=1;
            }
        }
        printf("Case #%d: %d\n",++kase,cnt);
    }
    return 0;
}

可统计的并查集
HDU3172 390ms
其实直接用rank记录friend数也可以
拖后腿的map应该可以用hash替代//1e5内的哈希已翻车
指针比引用稍快

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
using namespace std;
const int maxn = 1e5+7;
int p[maxn],r[maxn],f[maxn];
int maxx,n,m,a,b,cnt,pi,kase,cur;
string str1,str2;
map<string,int> mc; //char*无法判断 
inline void init(){
    mc.clear();
    for(int i = 1; i < maxn; i++) p[i]=i,f[i]=1;
    memset(r,0,sizeof r);
    cur = 1;
    str1.resize(30);
    str2.resize(30);
}
inline int find(int x){
    return p[x]==x?p[x]:p[x]=find(p[x]);//compress ok 
}
inline void link(int a,int b){
    a=find(a);b=find(b);
    if(a==b) return ;
    if(r[a]<r[b]) p[a]=b,f[b]+=f[a];
    else{
        p[b]=a;f[a]+=f[b];
        if(r[a]==r[b]) r[a]++;
    }
}
int main(){
    int T;
    while(scanf("%d",&T)!=EOF){
        while(T--){
            init();
            scanf("%d",&m);
            for(int i = 0; i < m; i++){
                scanf("%s%s",&str1[0],&str2[0]);
                int *ms1=&mc[str1],*ms2=&mc[str2];
                if(*ms1==0) *ms1=cur++;
                if(*ms2==0) *ms2=cur++;
                a=find(*ms1);b=find(*ms2);
                link(a,b);
                printf("%d\n",f[r[a]>r[b]?a:b]);
            }
        }
    }
    return 0;
}

LCA
参考:http://www.cnblogs.com/Aa1039510121/p/6657911.html

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e5;
int p[maxn],r[maxn],a[maxn];
bool vis[maxn];
void init(){
    for(int i = 0; i < maxn; i++) p[i]=i;
    memset(r,0,sizeof r);
    memset(a,0,sizeof a);
    memset(vis,0,sizeof vis);
}
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}
void link(int a,int b){
    a = find(a); b = find(b);
    if(x==y) return;
    if(r[x]<r[y]){
        p[x] = y;
        r[y]+=r[x];
    }
    else{
        p[y] = x;
        r[x]+=r[y];
    }
}
void lca(int u){
    a[u]=u;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(vis[v]) continue;
        lca(v);
        a[v] = u;
        link(u,v);
    }
    vis[u] = 1;
    for(int i = 0; i < Q[u].size(); i++){
        int v = Q[u][i];
        if(vis[v]) printf("%d\n",a[find(v)]);//LCA(u,v)
    } 
}

补题:https://vjudge.net/problem/CodeForces-722C
完全没想到可以用并查集维护区间
资料:http://www.cnblogs.com/DragoonKiller/p/4306169.html#3135295

UVA1160 既然并查集可以判联通,那也应该可以判环,题意当k种化合物的元素类型也为k时要统计,其实把一个当作边一个当作顶点就可以判环处理

if(uf.same(a,b)) cnt++;
else uf.link(a,b);

标签: 算法, 学习

添加新评论