Description

lxhgww 最近迷上了一款游戏, 在游戏里, 他拥有很多的装备, 每种装备都有 \(2\) 个属性, 这些属性的值用 \([1,10000]\) 之间的数表示. 当他使用某种装备时, 他只能使用该装备的某一个属性. 并且每种装备最多只能使用一次. 游戏进行到最后, lxhgww 遇到了终极 boss, 这个终极 boss 很奇怪, 攻击他的装备所使用的属性值必须从 \(1\) 开始连续递增地攻击, 才能对 boss 产生伤害. 也就是说一开始的时候, lxhgww 只能使用某个属性值为 \(1\) 的装备攻击 boss, 然后只能使用某个属性值为 \(2\) 的装备攻击 boss, 然后只能使用某个属性值为 \(3\) 的装备攻击 boss...... 以此类推. 现在 lxhgww 想知道他最多能连续攻击 boss 多少次?

Input

输入的第一行是一个整数 \(n\), 表示 lxhgww 拥有 \(n\) 种装备.

接下来 \(n\) 行, 是对这 \(n\) 种装备的描述, 每行 \(2\) 个数字, 表示第 \(i\) 种装备的 \(2\) 个属性值.

Output

输出一行, 包括 \(1\) 个数字, 表示 lxhgww 最多能连续攻击的次数.

Sample Input

3
1 2
3 2
4 5

Sample Output

2

Data Range

对于 30% 的数据, 保证 \(n \leq 1000\)

对于 100% 的数据, 保证 \(n \leq 10^6\)

Explanation

这道题我想了好久, 发现我是蒟蒻想不出来, 什么高大上的算法都上了还是没有正解 233

然后就想到了二分图或网络流, 再加上一个二分答案, 发现最糟时间一定是一个这道题看上 去无法搞定的时间复杂度 \(O(n^2 \log n)\).

然而看到 @hzwer 大神的题解标签就顿时想到了怎么做 (没有看题解). 后来问了一下 @Burst_Zero 大神发现他想了好久才想出并查集的做法 (居然直接想出来了好强啊).

就是说当且仅当每一个武器有两种攻击方式的时候可以用并查集做, 不然只能水网络流或二分图匹配加二分答案.

@hzwer 大神的题解大概是这个样子的:

发现这题的并查集做法真是惊呆了

把一个有 \(a, b\) 两种属性的武器看成点 \(a，b\) 之间的无向边

对于一个联通块, 假如不含环 (就是一棵树), 那么必定可以满足其中任意的 \(p - 1\) 个点.

对于一个联通块, 假如含环, 那么必定全部的 \(p\) 个点都能满足.

那么合并并查集的时候可以利用一个 vis 来维护这个性质

把权值看成点, 把武器看成边

如果每次加入的边是合并两个联通块

就把权值小的联通块并到权值大的联通块, 然后给权值小的 vis=true

如果不是

就把该联通块的顶点的 vis=true

这样就可以保证, 如果一个大小为 N 联通块

\(= n - 1\) 条边构成, 最大点的 vis=false, 其他为 true

\(\geq n\) 条边构成, 所有点的 vis=true

然后最后只要一次扫描 vis 就可以得出答案了

但是发现下面有这样两组数据 (我和 hzwer 的代码都过不了民间数据, 但是 BZOJ 居然 AC)

Input:
4
1 2
2 3
1 3
3 4

Output:
3
Input:
2
1 2
2 4

Output:
2

不管别的了 (第一次数组开的不够大直接 RE)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 1001000;

class UnionFindSet
{
public:
    int n, par[maxn], vmax[maxn];
    bool perfect[maxn];
    int find(int p)
    {
        if (par[p] == p)
            return p;
        par[p] = find(par[p]);
        return par[p];
    }
    void join(int p, int q)
    {
        p = find(p);
        q = find(q);
        // Ensure the larger point is the child.
        if (p > q)
            swap(p, q);
        if (p == q) {
            // vmax[q] = max(vmax[q], vmax[p]);
            perfect[q] = true;
        } else {
            perfect[p] = true;
            par[p] = q;
        }
        return ;
    }
    void init(int n)
    {
        this->n = n;
        for (int i = 1; i <= n; i++) {
            par[i] = i;
            // vmax[i] = i;
            perfect[i] = false;
        }
        return ;
    }
} graph;

int n;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    graph.init(n + 1);
    for (int i = 1, a, b; i <= n; i++) {
        scanf("%d%d", &a, &b);
        graph.join(a, b);
    }
    int res = 0;
    for (int i = 1; i <= n + 1; i++)
        if (!graph.perfect[i]) {
            res = i - 1;
            break;
        }
    printf("%d\n", res);
    return 0;
}