算法提高课汇总

并查集

基本操作

1. 合并两个集合, 集合用树的形式存储, 树的根节点作为集合的代表元素.

2. 查询某元素所在集合的代表元素(根节点).

优化

1. 路径压缩, 让集合所有元素均直接指向根节点.

2. 按秩合并, 合并两个集合时规定较低(元素较小集合)合并到较高集合内.

若只做一种优化, 并查集每次操作时间复杂度为$O(\lg{n})$, 同时做两种优化
每次操作时间复杂度可以认为是常数.

扩展

• 记录集合大小, 集合大小是集合内所有元素共有属性, 一般用根节点维护.

• 记录每个元素到根的距离, 每个元素各自维护. 可应用在需要维护多类集合的问题中.

理解题意

如果将网格点作为顶点, 画上的边作为边, 则问题为在图中添加边的操作过程中是否出现环.

• 判断是否有环: 若在添加边$(u, v)$前$u, v$已经属于同一联通快, 则加入边后构成环.

联通块的维护可以用并查集实现 — 在同一联通块的顶点视为在同一集合.

具体实现

实现时为方便并查集操作将二维网格点映射至一维, 映射函数为$f(x) = x \times n+y$,
注意此时$x, y$的起始坐标为$(0, 0)$.

代码实现 $O(m\lg{n})$

#include <iostream>

using namespace std;

const int N = 200 * 200 + 10;

int n, m;
int p[N];

int get(int x, int y)
{
    return x * n + y;
}

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


int main()
{
    cin >> n >> m;

    //初始化并查集
    for ( int i = 0; i < n * n; i ++ )  p[i] = i;

    int res = 0;
    for ( int i = 1; i <= m; i ++ )
    {
        int x, y; char op;
        cin >> x >> y >> op;
        x --, y --;

        int a = get(x, y), b;
        if ( op == 'D' )    b = get(x + 1, y);
        else    b = get(x, y + 1);

        int pa = find(a), pb = find(b);
        if ( pa == pb )
        {//已经属于同一联通块
            res = i;
            break;
        }
        p[pa] = pb; //将集合pa加入pb中
    }

    if ( !res ) puts("draw");
    else    cout << res << endl;

    return 0;
}