算法总结——并查集2

· · 算法·理论

并查集是一种树形数据结构，主要用于在图中找环、快速确定元素属于哪个集合和解决联通性问题。这篇文章是关于更杂的并查集问题。

例题1 [USACO16OPEN] Closing the Farm S

思路：

众所周知，并查集差分集合是非常麻烦的，以至于时间复杂度相当于重新建一遍并查集，因为删的时候你并不知道你让哪些本来不在一个集合的元素合并在了一起。所以暴力方法是每删一个点就重新建一遍并查集，看看是不是所有元素都在一个大集合里。时间复杂度 O((n+m)n) 。

我们完全可以把整个删点的过程反过来，变成一个一个的加点，每加一次算一次答案，存在一个数组里，最后再反着输出。这时候，我们可以把它优化到 O(n^2+m) 。但由于单次检查还是 O(n) 的，所以还是无法 AC 此题。

在每次加点的时候，被影响的只有与它连接的点的所在集合，也就是说，我们很多情况下都重复判断了。我们可以记一个 cnt ，表示当前集合数，当加点的时候，我们先让 cnt 加一，接着在连边的时候，如果连边的两头不属于同一集合，说明连上这条边将会将两个集合合二为一，所以 cnt 减一。每次检查的时候，只需要看 cnt 是不是 1 就可以了。

最终时间复杂度： O(n+m) 。

代码：

#include <bits/stdc++.h>
using namespace std;

int n,m,del[200005],tree[200005],cnt_kuai = 0;
vector<int>g[200005];
bool is_open[200005],ans[200005];

int find(int x)
{
    if(tree[x] == x) return x;
    return tree[x] = find(tree[x]);
}

void unionn(int x,int y)
{
    x = find(x);
    y = find(y);
    if(x != y) tree[x] = y;
    return;
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= m;i++)
    {
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1;i <= n;i++) tree[i] = i;
    for(int i = 1;i <= n;i++) cin >> del[i];
    for(int i = n;i >= 1;i--)
    {
        is_open[del[i]] = 1;
        cnt_kuai++;
        for(int j = 0;j < g[del[i]].size();j++)
        {
            if(is_open[g[del[i]][j]])
            {
                if(find(del[i]) != find(g[del[i]][j])) cnt_kuai--;
                unionn(del[i],g[del[i]][j]);
            }
        }
        ans[i] = (cnt_kuai == 1);
    }
    for(int i = 1;i <= n;i++)
    {
        if(ans[i]) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

例题2 [NOIP2017 提高组] 奶酪

思路：

这题可以用两种方法写，其中深搜的常会更小，时间会更短。

并查集：

我们可以把相互联通的空洞全部压成一个集合，再找若干对一个可以联通顶部，一个可以联通底部的空洞，如果其中出现了在同一集合的，说明有解，否则无解。

深搜：

如果一个洞联通底部就开一个深搜，如果其中有一个深搜一路搜到了顶部，就说明有解，如果没有一个到顶，无解。

代码：

并查集版：

#include <bits/stdc++.h>
using namespace std;

struct pos {long long x,y,z;} a[1005];
long long T,n,h,r,tree[1005];
bool flag;

long long dis(pos a,pos b)
{
    return  (a.x-b.x)*(a.x-b.x)+
            (a.y-b.y)*(a.y-b.y)+
            (a.z-b.z)*(a.z-b.z);
}

int find(int x)
{
    if(tree[x] == x) return x;
    return tree[x] = find(tree[x]);
}

void unionn(int x,int y)
{
    x = find(x);
    y = find(y);
    if(x != y) tree[x] = y;
    return;
}

bool check(void)
{
    for(int i = 1;i <= n;i++) tree[i] = i;
    for(int i = 1;i < n;i++)
    {
        for(int j = i+1;j <= n;j++)
        {
            if(dis(a[i],a[j]) <= (r+r)*(r+r)) unionn(i,j);
        }
    }
    for(int i = 1;i <= n;i++)
    {
        if(dis(a[i],{a[i].x,a[i].y,0}) <= r*r)
        {
            for(int j = 1;j <= n;j++)
            {
                if(dis(a[j],{a[j].x,a[j].y,h}) <= r*r && find(i) == find(j)) return 1;
            }
        }
    }
    return 0;
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T--)
    {
        cin >> n >> h >> r;
        for(int i = 1;i <= n;i++) cin >> a[i].x >> a[i].y >> a[i].z;
        if(check()) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

深搜版：

#include <bits/stdc++.h>
using namespace std;

struct pos {long long x,y,z;} a[1005];
long long T,n,h,r;
bool flag;
bool vis[1005];

long long dis(pos a,pos b)
{
    return  (a.x-b.x)*(a.x-b.x)+
            (a.y-b.y)*(a.y-b.y)+
            (a.z-b.z)*(a.z-b.z);
}

void dfs(long long x)
{
    vis[x] = 1;
    if(flag) return;
    if(dis(a[x],{a[x].x,a[x].y,h}) <= r*r)
    {
        flag = 1;
        return;
    }
    for(long long i = 1;i <= n;i++) if(vis[i] == 0 && dis(a[x],a[i]) <= (r+r)*(r+r)) dfs(i);
    return;
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T--)
    {
        cin >> n >> h >> r;
        for(int i = 1;i <= n;i++) cin >> a[i].x >> a[i].y >> a[i].z;
        memset(vis,0,sizeof(vis));
        flag = 0;
        for(int i = 1;i <= n;i++)
        {
            if(dis(a[i],{a[i].x,a[i].y,0}) <= r*r) dfs(i);
        }
        if(flag) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}