原题: ZOJ
3781 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3781

1.问题描述:

有N个对象,对象间可以连通。假设有一个命令用来连接两个对象,将两个对象传入该命令就会连接两者,还有一个命令来查询任意两个对象之间是否有连通的路径存在(间接相连也算)。以上即:合并命令、查找命令。

  • 连接是个等价关系,满足传递性、自反性、对称性等。
  • 连通分量:相互连接的对象的最大集合,连通分量重的任意两个对象都是相连接的。

题意:

2.快速查找算法:

给一个n*m的X,O构成的格子,对一个点操作可以使与它相连通的所有一样颜色的格子翻转颜色(X->O或O->X),问给定的矩阵最少操作多少次可以全部变成一样的颜色。

2.1算法描述(贪心):

维护一个简单的对象索引整数数组,相互连通的对象对应的数组值相等,不连通的不相等。

  • 查找:如果p和q对应的数组值相同则它们俩连通。
  • 连通:将两组索引id转为一致。

图片
  效率:初始化O(n),并O(n),查O(1)。如果要在n个对象上进行n次合并操作,则是O(n2),很不合理。

网上思路:

2.2代码实现:

public class UF{ private int[] id; UF(int N){ //构造器 id = new int[N]; for(int i = 0;i < N;i++) id[i] = i; } void union(int p,int q){//并 int pid = id[p]; int qid = id[q]; for(int i = 0;i < id.length;i ++) if(id[i] == pid) id[i] = qid; } boolean connected(int p,int q){//查 return id[p] == id[q]; } public static void main(String args[]){ int N = StdIn.readInt(); UF uf = new UF(N); while(!StdIn.isEmpty()){ int p = StdIn.readInt(); int q = StdIn.readInt(); if(!uf.connected(p,q)){ uf.union(p,q); StdOut.println(p + " " + q); } } } }

每次操作都将本身所在的连通块与和自己相邻的不同颜色的连通块变成同一种颜色,也就是变成一个连通块了,那么要使n次操作后全部变成一样的颜色,也就是从某点出发到达其余所有点。所以先dfs把连通块缩成点,然后相邻的连通块之间建边,枚举以每个点为根的情况,bfs求出每种情况的深度,取最小的即为答案。

3.快速合并算法

思路很重要,实现起来不难。

3.1算法描述:

运用了懒计算的思路,维护一棵树,id[i]记录着i的父节点。

  • 查找就是找p和q是否有同一祖先节点。
  • 合并p和q就是将p的祖先节点置为q的祖先节点,反之亦可。

图片
  初始化O(n),并O(n),查O(n)。如果树特别高,则查特别耗时。

代码:

3.2代码实现:

public class UF{ private int[] id; UF(int N){ //构造器 id = new int[N]; for(int i = 0;i < N;i++) id[i] = i; } void union(int p,int q){//并 while(p != id[p]) p = id[p] while(q != id[q]) q = id[q]; id[p] = q; } boolean connected(int p,int q){//查 while(p != id[p]) p = id[p] while(q != id[q]) q = id[q]; return p == q; } public static void main(String args[]){ int N = StdIn.readInt(); UF uf = new UF(N); while(!StdIn.isEmpty()){ int p = StdIn.readInt(); int q = StdIn.readInt(); if(!uf.connected(p,q)){ uf.union(p,q); StdOut.println(p + " " + q); } } } }

图片 1图片 2

4.快速合并算法改进算法1:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#define Mod 1000000007
using namespace std;
#define N 44

char ss[N][N];
int ind[N][N],vis[N][N];
int now,n,m;
int inq[1630];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
vector<int> G[2001];

struct node
{
    int dis,ind;
};

int OK(int nx,int ny)
{
    if(nx < n && nx >= 0 && ny < m && ny >= 0)
        return 1;
    return 0;
}

void dfs(int nx,int ny,int now)
{
    for(int k=0;k<4;k++)
    {
        int kx = nx + dx[k];
        int ky = ny + dy[k];
        if(!OK(kx,ky))
            continue;
        if(ss[kx][ky] == ss[nx][ny])
        {
            if(ind[kx][ky] == -1)
            {
                ind[kx][ky] = now;
                dfs(kx,ky,now);
            }
        }
        else if(ind[kx][ky] != -1) //已经有标号,连边
        {
            int v = ind[kx][ky];
            G[v].push_back(now);
            G[now].push_back(v);
        }
    }
}

int SPFA(int num)
{
    queue<node> que;
    memset(inq,0,sizeof(inq));
    node S,tmp,now;
    S.dis = 0;
    S.ind = num;
    int res = 0;
    que.push(S);
    inq[num] = 1;
    while(!que.empty())
    {
        tmp = que.front();
        que.pop();
        res = max(res,tmp.dis);
        now.dis = tmp.dis + 1;
        for(int i=0;i<G[tmp.ind].size();i++)
        {
            now.ind = G[tmp.ind][i];
            if(!inq[now.ind])
            {
                inq[now.ind] = 1;
                que.push(now);
            }
        }
    }
    return res;
}

int main()
{
    int i,j,k;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=0;i<n;i++)
            scanf("%s",ss[i]);
        now = 1;
        memset(ind,-1,sizeof(ind));
        for(i=0;i<=n*m;i++)
            G[i].clear();
        for(i=0;i<n;i++)
            for(j=0;j<m;j++)
                if(ind[i][j] == -1)
                {
                    ind[i][j] = now;
                    dfs(i,j,now);
                    now++;
                }
        int ans = Mod;
        for(i=1;i<now;i++)
            ans = min(ans,SPFA(i));
        printf("%d\n",ans);
    }
    return 0;
}

4.1算法描述:

我们要避免得到很高的树,当一颗大树和一颗小树合并,避免将大树放到小树下面(这样会使树变高)。

用加权实现,权重是每棵树中对象的个数。通过确保将小树的根节点作为大树的根节点的子节点以维持平衡。

初始化O(n),并O(logn) ,查O(logn),因为任意节点X的深度最多是logn。

View Code

4.2快速合并算法改进算法代码实现:

public class UF{ private int[] id; UF(int N){ //构造器 id = new int[N]; sz = new int[N]; for(int i = 0;i < N;i++) id[i] = i; sz = 1; } void union(int p,int q){//并 while(p != id[p]) p = id[p] while(q != id[q]) q = id[q]; if(p == 1) return; if(sz[p] < sz[q]) {id[p] = q;sz[p]+= sz[q];} else {id[q] = p;sz[q]+= sz[p];} } boolean connected(int p,int q){//查 while(p != id[p]) p = id[p] while(q != id[q]) q = id[q]; return p == q; } public static void main(String args[]){ int N = StdIn.readInt(); UF uf = new UF(N); while(!StdIn.isEmpty()){ int p = StdIn.readInt(); int q = StdIn.readInt(); if(!uf.connected(p,q)){ uf.union(p,q); StdOut.println(p + " " + q); } } } }

 

5.快速合并算法改进算法2:

5.1算法描述:

使用路径压缩的加权算法,即当我们经过”递推”找到祖先节点后,”回溯”的时候顺便将它的子孙节点都直接指向祖先,这样以后再次查时复杂度就变成O(1)了,再回溯一次将树展平。这是最优算法。

初始化O(n),并和查都非常接近但是仍没达到1(均摊成本)。

5.2算法代码:

public class UF{ private int[] id; UF(int N){ //构造器 id = new int[N]; sz = new int[N]; for(int i = 0;i < N;i++) id[i] = i; sz = 1; } void union(int p,int q){//并 while(p != id[p]){ id[p] = id[id[p]]; p = id[p] } while(q != id[q]){ id[q] = id[id[q]]; q = id[q]; } if(p == 1) return; if(sz[p] < sz[q]) {id[p] = q;sz[p]+= sz[q];} else {id[q] = p;sz[q]+= sz[p];} } boolean connected(int p,int q){//查 while(p != id[p]){ id[p] = id[id[p]]; p = id[p]; } while(q != id[q]){ id[q] = id[id[q]]; q = id[q]; } return p == q; } public static void main(String args[]){ int N = StdIn.readInt(); UF uf = new UF(N); while(!StdIn.isEmpty()){ int p = StdIn.readInt(); int q = StdIn.readInt(); if(!uf.connected(p,q)){ uf.union(p,q); StdOut.println(p + " " + q); } } } }

admin

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注