再说并查集

上一次写并查集是在看《数据结构》的时候写了树模型的拓展,当时那一章讲到了并查集,并提出了基本的思想。

并查集是我在第一次寒假集训学到的,当时学完写了总结月球美容计划之并查集

今天在看生成树的时候,图论那本书又讲到了并查集。

经过各种资料的查阅,确定并查集并没有特别深入的应用,并查集只不过就是一种判断集合属性的方法,说白了,就是有若干种关系,判断谁和谁是同一种关系。

并查集算法是由3个函数组成的,就三个函数:

初始化函数

根据初始化的不同,并查集有两种写法,这两种写法没有优劣差异,就是初始化不同而已。

初始化为-1

int bc[100];

int UFset1()
{
    for(int i = 0;i < 100;i++)
        bc[i] = -1;
}

初始化为-1是《数据结构》和《图论》都采取的方法,但我学的时候是使用的第二种初始化

初始化为下标

int UFset2()
{
    for(int i = 0;i < 100;i++)
        bc[i] = i;
}

初始化的不同,在剩下两个函数直接造成细节上的差异,但是并没有造成时间复杂度和空间复杂度的差异。

查找函数

查找函数便是用来查找任一元素的根结点(祖先),而在并查集算法中,唯一的优化便是对查找函数的优化。

未优化的查找函数

//初始化为-1
int fin1 (int a)  //查
{
    int r = a;

    while (-1 != bc[r])
        r = bc[r];

    return r;
}

//初始化为下标
int fin2 (int a)  //查
{
    int r = a;

    while (r != bc[r])
        r = bc[r];

    return r;
}

因为并查集数组bc[],存储的是当前结点的父结点,溯流而上,就能找到根结点,找到之后便返回根结点。

对查找函数的优化

//初始化为-1
int fin1 (int a)  //查
{
    int r = a;

    while (-1 != bc[r])
        r = bc[r];

    while (r != bc[a])  //优化,压缩路径
    {
        int t = bc[a];
        a = bc[a];
        bc[t] = r;
    }

    return r;
}

//初始化为下标
int fin2 (int a)  //查
{
    int r = a;

    while (r != bc[r])
        r = bc[r];

    while (r != bc[a])  //优化,压缩路径
    {
        int t = bc[a];
        a = bc[a];
        bc[t] = r;
    }

    return r;
}

因为bc数组是记录前驱(父结点)的一棵多叉树,那么如果存在最坏情况(整棵树是线形存在),那么每次查找将最高消耗O(n),也就是说,如果树的深度越低,那么,查找效率越高。因此对其优化、压缩路径。

合并函数

我们可以用查找函数来判断是非属于同一个集合,用合并函数来把两个集合合并成一个集合。

对于合并集合,函数,初始化成什么对其没有影响。

void Union(int R1,int R2)
{
    int fa = fin(R1),fb = fin(R2);
    bc[fa] = fb;
}

 进一步优化

在图论这本书了提到了一个灰常奇妙的优化。

原理很简单,这个并查集浪费时间在查找上,因为如果树长的很奇葩(线形),那么查找时间将灰常壮观,因此,在查找函数中对其压缩路径,来解决这个问题,那么压缩完路径之后,深度不超过3,那么,查找的时间复杂度解决了,但是还有一个东西浪费时间,就是压缩路径本身。

这样想,如果我们在建树的过程中就尽量让树平衡(相关概念参考:数据结构之二叉树),那么在压缩路径的时候,也会节省一些时间。

至于怎么实现,书中给出的解决方案是靠根结点来记录这个根结点下有多少子节点。

首现,要选择初始化为-1的那种方案,然后对查找进行修改

//初始化为-1
int fin1 (int a)  //查
{
    int r = a;

    while (bc[r] >= 0)  //在这里修改了,
        r = bc[r];      //因为如果是根结点,其值为负数而不仅为-1

    while (r != bc[a])  //优化,压缩路径
    {
        int t = bc[a];
        a = bc[a];
        bc[t] = r;
    }

    return r;
}

然后对合并函数进行修改:

void Union(int R1,int R2)
{
    int fa = fin(R1),fb = fin(R2);
    int tmp = bc[fa] + bc[fb];  //结点个数、负数

    if(bc[fa] > bc[fb])    //加权法则
    {
        bc[fa] = fb;
        bc[fb] = tmp;
    }else
    {
        bc[fb] = fa;
        bc[fa] = tmp;
    }
}
2015/01/22 13:00 下午 posted in  算法&数据结构

深度优先搜索(DFS)的奇偶剪枝

今天进行到DFS&&BFS&&活动网络问题。BFS和DFS可以解决很多有趣的问题,而BFS和DFS本身就有很多优化、变形。对于对于优化最常见的莫过于剪枝了,而对于搜索剪枝,最常见的也就是奇偶剪枝。

对于DFS,详情见数据结构之图的遍历

对于DFS剪枝,那ZOJ2110作为例子:Tempter of the Bone

先看没有剪枝和剪枝之后的效果:

为什么剪枝

因为DFS和BFS可以是认为树形搜索的。因此,他们的搜索轨迹可以生成出深度优先生成树和广度优先生成树,详情见: 图的连通性

如果我们在生成树的过程中(就是查找过程中),发现并确定一个分支不可能找到解,那么我们就把这个分支剪掉,以节省时间。这就是剪枝。

奇偶剪枝

首先我们要知道一个前提:

奇数 + 偶数 = 奇数
偶数 + 偶数 = 偶数

那么,也就可以推出:

偶数 = 奇数 - 奇数

偶数 = 偶数 - 偶数

假设有这么一个地图:

我们可以发现一个规律,从其中任意一个0到任意一个0需要偶数步,而其中任意一个1到任意一个0需要奇数步。

如果我们每一步的消耗时间是相同的,那么,需要用时和最短的步数必须需要同奇偶才能到达,否者不会到达。

为了方便描述,我们假设我们在(sx,sy)的位置,需要消耗t时到达(ex,ey)。

那么不管我们怎么绕圈,如果 t-[abs(ex-sx)+abs(ey-sy)] 结果为非偶数(奇数),则无法在t步恰好到达。

因此,这样我们就可以在搜索过程中,实时判断现在剩下的时间和现在位置到目的地最短距离是否同奇偶,如果不是,那么就没有必要搜索下去了。

骨头问题

再回到ZOJ2110,这个题用到了奇偶剪枝,并且还有一种搜索前优化,就是如果所有狗狗能走的位置(所有的地图位置的个数减去障碍物的个数)小于规定时间,直接打印NO(就是狗狗根本跑不开,就不用搜索了)。

代码:

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

char mp[10][10];
int bj[10][10];
int chx[] = {0,1,0,-1};
int chy[] = {1,0,-1,0};
int n,m,t;
int ex,ey;
int tf;

void dfs(int x,int y,int tim)
{
    if(x < 0 || y < 0 || x >= n || y >= m)
        return ;

    if(tim == t && x == ex && y == ey)
    {
        cout << "YES" << endl;
        tf = 1;
        return ;
    }

    int tmp = (t - tim) - fabs(x - ex) - fabs(y - ey);

    if(tmp < 0 || tmp % 2)
        return ;

    for(int i = 0; i < 4;i++)
    {
        if(mp[x + chx[i]][y + chy[i]] != 'X')
        {
            mp[x + chx[i]][y + chy[i]] = 'X';
            dfs(x + chx[i],y + chy[i],tim + 1);
            if(tf)
                return ;
            mp[x + chx[i]][y + chy[i]] = '.';
        }
    }
}

int main()
{
    while(cin >> n >> m >> t,n)
    {
        tf = 0;
        memset(bj,-1,sizeof(bj));
        for(int i = 0;i < n;i++)
            cin >> mp[i];

        int x,y;

        for(int i = 0;i < n;i++)
        {
            int j;
            for(j = 0;j < m;j++)
                if(mp[i][j] == 'S')
                {
                    x = i;
                    y = j;
                    break;
                }
            if(j < m)
                break;
        }

        for(int i = 0;i < n;i++)
        {
            int j;
            for(j = 0;j < m;j++)
                if(mp[i][j] == 'D')
                {
                    ex = i;
                    ey = j;
                    break;
                }
            if(j < m)
                break;
        }

        mp[x][y] = 'X';
        dfs(x,y,0);

        if(!tf)
            cout << "NO" << endl;
    }
    return 0;
}
2015/01/21 12:57 下午 posted in  算法&数据结构

可图和Havel-Hakimi定理

可图(Graphic)

什么是可图,那需要先说一下度序列。

度序列是把图的多有顶点度数排列成一个序列s,则称s为图G的度序列。

度序列可以是按照顶点的顺序排列,也可以按照递增、递减的顺序排列。所谓的可图,是建立在度序列的基础上的。

序列是可图的:一个非负整数组成的有限序列如果是某个无向图的度序列,则称这个序列是可图的。

说白了,就是如果一串度序列可以逆向生成出图,就是可图的。而判断一个序列是否是可图的,则由Havel-Hakimi定理判断。

Havel-Hakimi定理

由非负整数组成的非增序列s:d1,d2,...,dn(n>=2,d1>=1)是可图的,当且仅当序列:

s1:d2 - 1,d3 - 1,...,dd1+1 - 1,dd1+2,...,dn

是可图的。序列s1中有n-1个非负整数,s序列中d1后的前d1个度数(即d2~dd1+1)减1后构成s1中的前d1个数。

说白了就是先把第一个点(度数为d1)连线到后面d1个点,保证第一个点度数满足,然后再以此类推考虑后面的点。如果后面所有顶点满足并且度数不多不少(最后不剩,过程中没有度数为负数),即可认为,度序列是可图的。

青蛙邻居问题

POJ1659 Frogs' Neighborhood

Description

未名湖附近共有N个大小湖泊L1, L2, ..., Ln(其中包括未名湖),每个湖泊Li里住着一只青蛙Fi(1 ≤ iN)。如果湖泊LiLj之间有水路相连,则青蛙FiFj互称为邻居。现在已知每只青蛙的邻居数目x1, x2, ...,xn,请你给出每两个湖泊之间的相连关系。

Input

第一行是测试数据的组数T(0 ≤ T ≤ 20)。每组数据包括两行,第一行是整数N(2 1, x2,..., xn(0 ≤ xiN)。

Output

对输入的每组测试数据,如果不存在可能的相连关系,输出"NO"。否则输出"YES",并用N×N的矩阵表示湖泊间的相邻关系,即如果湖泊i与湖泊j之间有水路相连,则第i行的第j个数字为1,否则为0。每两个数字之间输出一个空格。如果存在多种可能,只需给出一种符合条件的情形。相邻两组测试数据之间输出一个空行。

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int G[20][20];
struct Node
{
    int dnum;
    int no;
}d[20];

int cmp(Node a,Node b)
{
    return a.dnum > b.dnum;
}

int main()
{
    int N;
    cin >> N;

    while(N--)
    {
        bool flag = 1;
        memset(G,0,sizeof(G));

        int n;
        cin >> n;

        for(int i = 0;i < n;i++)
        {
            cin >> d[i].dnum;
            d[i].no = i;
        }

        for(int i = 0;i < n;i++)
        {
            sort(&d[i],&d[i] + n - i,cmp);
            int last = d[i].dnum;
            d[i].dnum = 0;
            if(last > n - i)
            {
                flag = 0;
                break;
            }

            for(int j = i + 1;j <= i + last;j++)
            {
                if(d[j].dnum - 1 >= 0)
                {
                    G[d[i].no][d[j].no] = 1;
                    G[d[j].no][d[i].no] = 1;
                    d[j].dnum -= 1;
                }else
                {
                    flag = 0;
                }
                if(!flag)
                    break;
            }
            if(!flag)
                break;
        }

        if(flag)
        {
            for(int i = 0;i < n;i++)
                if(d[i].dnum > 0)
                    flag = 0;
        }

        if(!flag)
            cout << "NO" << endl;
        else
        {
            cout << "YES" << endl;

            for(int i = 0;i < n;i++)
                for(int j = 0;j < n;j++)
                    cout << G[i][j] << (j < n - 1 ? ' ' : 'n');
        }

        if(N)
            cout << endl;
    }
    return 0;
}

 注意

这个题目是Special Judge,也就是说这个题的答案是有多种的。这个是由Havel-Hakimi定理导致的,由于可图是由度数重构图,这个过程构建的图可能不是唯一的

2015/01/20 12:56 下午 posted in  算法&数据结构

关键路径

AOE网

与AOV网相对应的是AOE网,即边表示活动的网。AOE网是一个带权的有向无环图,其中,定点表示事件,弧表示活动,权表示活动持续的时间。通常,AOE网可以用来估算工程的完成时间。

关键路径

设一个工程有11项活动,9个事件,事件 V1表示整个工程开始,事件V9——表示整个工程结束,问题:

  • 完成整项工程至少需要多少时间?
  • 哪些活动是影响工程进度的关键?

关键路径的几个术语

  • 路径长度:路径上各活动持续时间之和。
  • 关键路径:路径长度最长的路径。
  • 关键活动:关键路径上的活动,即这些活动的时间延迟或提前会影 响整个工程工期的延迟或提前。

我们可以说,我们可以对一个工程计划,先从头开始保证每个任务尽快完成,那么就可以计算出每个点的最短完成时间。

如果我们从尾开始,以尾的最快完成时间为期限,再逆推每个点最迟完成时间且保证不耽误尾节点的完成,那么就可以计算出每个点的最晚完成时间。

那么一个节点完成时间是在最早完成时间到最晚完成时间的区间内则不会影响整个工程的进度,如果一个节点最早完成时间和最晚完成时间相同,就意味着,如果这个节点延误了,整个工程将被延误。那么,这就是关键活动

换句话,如果找到关键活动,如果加快关键活动的完成,整个工程将更快完成。

Ve(j):表示事件Vj的最早发生时间。

Vl(j):表示事件Vj的最迟发生时间。

e(i):表示活动ai的最早开始时间。

l(i):表示活动ai的最迟开始时间。

l(i)-e(i):表示完成活动ai的时间余量。

若时间余量为0,则该活动为关键活动,所在的路径为关键路径。

设活动ai用弧表示,其持续时间记为:dut() 则有:

  • e(i)=Ve(j)
  • l(i)=Vl(k)-dut()

求Ve(j)和Vl(j)需分两步进行:

  1. 从Ve(0)=0开始向前推进:Ve(j)=Max{Ve(i) + dut()(每条指向j的边)}
  2. 从Vl(n-1)=Ve(n-1)起向后推进:Vl(i)=Min{Vl(j)-dut()(每条指向j的边)}

这样,就能找到每个关键活动。

因此,可以提炼算法:

  1. 输入e条弧建立AOE网的存储结构
  2. 从源点v0出发,令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i]。如果得到的拓扑有序序列中顶点个数小于网中各顶点数n,则说明网中存在环,不能求关键路径,算法终止,否者执行第3步
  3. 从汇点vn出发,令vl[n-1]=ve[n-1],按逆拓扑有序求其余各顶点的最迟发生时间vl[i]
  4. 根据各顶点的ve和vl值,求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足e(s)=l(s),则为关键活动

伪代码:

Status TopologicalOrder(ALGraph G, Stack &T) {
  // 有向网G采用邻接表存储结构,求各顶点事件的最早发生时间ve(全局变量)。
  // T为拓扑序列定点栈,S为零入度顶点栈。
  // 若G无回路,则用栈T返回G的一个拓扑序列,且函数值为OK,否则为ERROR。
  Stack S;int count=0,k;
  char indegree[40];
  ArcNode *p;
  InitStack(S);
  FindInDegree(G, indegree);  // 对各顶点求入度indegree[0..vernum-1]
  for (int j=0; jnextarc) {
      k = p->adjvex;            // 对j号顶点的每个邻接点的入度减1
      if (--indegree[k] == 0) Push(S, k);   // 若入度减为0,则入栈
      if (ve[j]+p->info > ve[k])  ve[k] = ve[j]+p->info;
    }//for  *(p->info)=dut()
  }//while
  if (countnextarc) {
      k=p->adjvex;  dut=p->info;     //dut
      if (vl[k]-dut nextarc) {
      k=p->adjvex;dut=p->info;
      ee = ve[j];  el = vl[k]-dut;
      tag = (ee==el) ? '*' : ' ';
      printf(j, k, dut, ee, el, tag);   // 输出关键活动
    }
  return OK;
} // CriticalPath

 关键路径分析

  • 求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径;
  • 只有缩短关键活动的工期才有可能缩短工期;
  • 关键路径可能不只一条,要同时提高所有的关键路径,才能缩短整个工期;
  • 若一个关键活动不在所有的关键路径上,减少它并不能减少工期;
  • 只有在不改变关键路径的前提下,缩短关键活动才能缩短整个工期。
2014/12/23 12:54 下午 posted in  算法&数据结构

拓扑排序

什么是拓扑排序

拓扑排序,简单地说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

偏序形式定义: 设R是集合A上的一个二元关系,若R满足: Ⅰ 自反性:对任意x∈A,有xRx; Ⅱ 反对称性(即反对称关系):对任意x,y∈A,若xRy,且yRx,则x=y; Ⅲ 传递性:对任意x, y,z∈A,若xRy,且yRz,则xRz。[1] 则称R为A上的偏序关系,通常记作≼。注意这里的≼不必是指一般意义上的“小于或等于”。 若然有x≼y,我们也说x排在y前面(x precedes y)。——摘自百度百科 全序形式定义: 设集合X上有一全序关系,如果我们把这种关系用 ≤ 表述,则下列陈述对于 X 中的所有 a, b 和 c 成立: 如果 a ≤ b 且 b ≤ a 则 a = b (反对称性) 如果 a ≤ b 且 b ≤ c 则 a ≤ c (传递性) a ≤ b 或 b ≤ a (完全性) 配对了在其上相关的全序的集合叫做全序集合(totally ordered set)、线序集合(linearly ordered set)、简单序集合(simply ordered set)或链(chain)。链还常用来描述某个偏序的全序子集,比如在佐恩引理中。 关系的完全性可以如下这样描述:对于集合中的任何一对元素,在这个关系下都是相互可比较的。 注意完全性条件蕴涵了自反性,也就是说,a ≤ a。因此全序也是偏序(自反的、反对称的和传递的二元关系)。全序也可以定义为“全部”的偏序,就是满足“完全性”条件的偏序。 可作为选择的,可以定义全序集合为特殊种类的格,它对于集合中的所有 a, b 有如下性质: 我们规定 a ≤ b 当且仅当。可以证明全序集合是分配格。 全序集合形成了偏序集合的范畴的全子范畴,通过是关于这些次序的映射的态射,比如,映射 f 使得"如果 a ≤ b 则 f(a) ≤ f(b)"。 在两个全序集合间的关于两个次序的双射是在这个范畴内的同构。——摘自百度百科

一个表示偏序的有向图可用来拜师一个流程图。它或者是一个施工流程图,或者是一个产品生产的流程图,再或是一个数据流图(每个顶点表示一个过程)。图中每一条有向边表示两个子工程之间的次序关系(领先关系)。

 怎么获得拓扑排序

  1. 在有向图中选一个没有前驱的顶点且输出之
  2. 从图中删除该顶点和所有以它为尾的弧
  3. 重复上述两步直到所有顶点均已输出或当前图中不存在无前驱的顶点为止

如果发现无前驱的顶点,可以说明图中存在环。 伪代码实现:

Status TopologicalSort(ALGraph G) {
  // 有向图G采用邻接表存储结构。
  // 若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则ERROR。
  SqStack S;
  int count,k,i;
  ArcNode *p;
  char indegree[MAX_VERTEX_NUM];
  FindInDegree(G, indegree);   // 对各顶点求入度indegree[0..vernum-1]
  InitStack(S);
  for (i=0; i<G.vexnum; ++i)       // 建零入度顶点栈S
    if (!indegree[i]) Push(S, i);  // 入度为0者进栈
  count = 0;                       // 对输出顶点计数
  while (!StackEmpty(S)) {
    Pop(S, i);
    printf(i, G.vertices[i].data);  ++count;  // 输出i号顶点并计数
    for (p=G.vertices[i].firstarc;  p;  p=p->nextarc) {
      k = p->adjvex;               // 对i号顶点的每个邻接点的入度减1
      if (!(--indegree[k])) Push(S, k);  // 若入度减为0,则入栈
    }
  }
  if (count<G.vexnum) return ERROR;      // 该有向图有回路
  else return OK;
} // TopologicalSort
2014/12/18 12:53 下午 posted in  算法&数据结构