算法总结—并查集2

· · 算法·理论

直接看题目：

\text{\scriptsize{USACO}:\scriptsize{Closing\ the\ Farm\ S}}

银组题

这道题数据范围很小，每询问一次就跑一遍并查集，并统计一共有多少个不交集。时间复杂度 O(n^2) 。

注意：

代码

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
struct node{
    int u,v;
}a[3005];
int father[3005];
bool vis[3005];
bool cmp(node q,node h){
    if(q.u==h.u){
        return q.v<h.v;
    }
    return q.u<h.u; 
}
int find1(int x){
    if(father[x]==x){
        return x;
    }
    father[x]=find1(father[x]);
    return father[x];
}
void union1(int x,int y){
    x=find1(x);
    y=find1(y);
    if(x!=y){
        father[x]=y;
    }
    return;
}
bool check(int x){
    for(int i=1;i<=n;i++){
        father[i]=i;
    }
    for(int i=1;i<=m;i++){
        if(vis[a[i].u]==1||vis[a[i].v]==1){
            continue;
        }
        union1(a[i].u,a[i].v);
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(vis[i]){
            continue;
        }
        if(father[i]==i){
            cnt++;
        }
    }
    return (cnt==1);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i].u>>a[i].v;
        if(a[i].u>a[i].v){
            swap(a[i].u,a[i].v);
        }
    }
    sort(a+1,a+1+m,cmp);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(check(x)){
            cout<<"YES\n";
        }else{
            cout<<"NO\n";
        }
        vis[x]=1;
    }
    return 0;
}

金组题

这道题 n 可能达到 2\times10^5 ，O(n^2) 肯定是不行了，那我们该怎么建并查集呢？

思路

我们设没有删点之前的序列为 \tt 1\ 2\ 3\ 4\ 5 。\ 删掉一次后是 \tt 2\ 3\ 4\ 5 。\ 删掉二次后是 \tt 3\ 4\ 5 。\ 删掉三次后是 \tt 4\ 5 。\ 删掉四次后是 \tt 5 。\ 删除一次的时间复杂度为 O(n) ，太慢了，于是我们反过来想：添加点 。

不过添加点极限还是 O(n) 仍会 \text{\small{TLE}} ，于是我们有会得到如下策略：首先无论如何，先把集合数量加一，每次添加边时，如果两个点同属一个集合，就将集合数量减一。每次循环过后，如果集合数量等于 1 ，就是说添加后任意两个都可以到达；如果集合数量不等于 1 ，就是说添加后任意两个点不一定可以到达。

代码

#include<iostream>
#include<vector>
using namespace std;
int n,m;
int father[200005];
vector<int>vec[200005];
int cnt=0;
string ans[200005];
int a[200005];
bool vis[200005];
int find1(int x){
    if(father[x]==x){
        return x;
    }
    father[x]=find1(father[x]);
    return father[x];
}
void union1(int x,int y){
    x=find1(x);
    y=find1(y);
    if(x!=y){
        cnt--;
        father[x]=y;
    }
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        vec[u].push_back(v);
        vec[v].push_back(u);
    } 
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        father[i]=i;
    }
    for(int i=n;i>=1;i--){
        vis[a[i]]=1;
        cnt++;
        for(int j=0;j<vec[a[i]].size();j++){
            if(vis[vec[a[i]][j]]==1){
                union1(vec[a[i]][j],a[i]);
            }
        }
        if(cnt==1){
            ans[i]="YES";
        }else{
            ans[i]="NO";
        }
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}

奶酪

这道题就是将相交或相切的两个洞合并，看连着桌子的洞和奶酪顶部的洞是否属于同一个集合内。

所以这道题我们只需要判断两个点之间是否相离或相切，如果是合并即可，不过初始化时，记得把 0 和 n+1 也判掉。

代码

#include<iostream>
#include<cmath>
using namespace std;
struct node{
    double x,y,z;
}a[1005];
int father[1005];
int find1(int x){
    if(father[x]==x){
        return x;
    }
    father[x]=find1(father[x]);
    return father[x];
}
void union1(int x,int y){
    x=find1(x);
    y=find1(y);
    if(x!=y){
        father[x]=y;
    }
    return;
}
double dis(double x_1,double x_2,double y_1,double y_2,double z_1,double z_2){
    double x=(x_1-x_2)*(x_1-x_2);
    double y=(y_1-y_2)*(y_1-y_2);
    double z=(z_1-z_2)*(z_1-z_2);
    return sqrt(x+y+z);
}
void work(){
    double n,h,r;
    cin>>n>>h>>r;
    for(int i=0;i<=n+1;i++){
        father[i]=i;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y>>a[i].z;
        if(a[i].z+r>=h){
            union1(n+1,i);
        }
        if(a[i].z<=r){
            union1(0,i);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(dis(a[i].x,a[j].x,a[i].y,a[j].y,a[i].z,a[j].z)<=2.00*r){
                union1(i,j);
            }
        }
    }
    if(find1(0)==find1(n+1)){
        cout<<"Yes\n";
    }else{
        cout<<"No\n";
    }
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        work();
    }
    return 0;
}

营救

二分答案最大拥挤度，每枚举一次，就重新跑一边并查集，并且判断 s 和 t 是否同属一个集合。时间复杂度 O((n+m)\log \max\{w_i\}) 。

代码

#include<iostream>
#define int long long
using namespace std;
int n,m,s,t;
struct node{
    int u,v,w;
}a[20005];
int father[10005];
int find1(int x){
    if(father[x]==x){
        return x;
    }
    father[x]=find1(father[x]);
    return father[x];
}
void union1(int x,int y){
    x=find1(x);
    y=find1(y);
    if(x!=y){
        father[x]=y;
    }
    return;
}
bool check(int x){
    for(int i=1;i<=n;i++){
        father[i]=i;
    }
    for(int i=1;i<=m;i++){
        if(a[i].w<=x){
            union1(a[i].u,a[i].v);
        }
    }
    return find1(s)==find1(t);
}
signed main(){
    cin>>n>>m>>s>>t;
    int l=0,r=-1e9;
    for(int i=1;i<=m;i++){
        cin>>a[i].u>>a[i].v>>a[i].w;
        r=max(r,a[i].w);
    }
    r++;
    while(l+1<r){
        int mid=(l+r)/2;
        if(check(mid)){
            r=mid;
        }else{
            l=mid;
        }
    }
    cout<<r;
    return 0;
}