Link: D. Segment Tree

D. Segment Tree

Description:
As the name of the task implies, you are asked to do some work with segments and trees.

Recall that a tree is a connected undirected graph such that there is exactly one simple path between every pair of its vertices.

You are given n segments [l1,r1],[l2,r2],…,[ln,rn], li<ri for every i. It is guaranteed that all segments' endpoints are integers, and all endpoints are unique — there is no pair of segments such that they start in the same point, end in the same point or one starts in the same point the other one ends.

Let's generate a graph with n vertices from these segments. Vertices v and u are connected by an edge if and only if segments [lv,rv] and [lu,ru] intersect and neither of it lies fully inside the other one.

For example, pairs ([1,3],[2,4]) and ([5,10],[3,7]) will induce the edges but pairs ([1,2],[3,4]) and ([5,7],[3,10]) will not.

Determine if the resulting graph is a tree or not.

Input
The first line contains a single integer n (1≤n≤5⋅1e5) — the number of segments.

The i-th of the next n lines contain the description of the i-th segment — two integers li and ri (1≤li<ri≤2n).

It is guaranteed that all segments borders are pairwise distinct.

Output
Print "YES" if the resulting graph is a tree and "NO" otherwise.

Examples
input
6
9 12
2 11
1 3
6 10
5 7
4 8
output
YES
input
5
1 3
2 4
5 9
6 8
7 10
output
NO
input
5
5 8
3 6
2 9
7 10
1 4
output
NO

Problem solving:
这道题的意思就是给你n个线段，并且告诉你这n个线段的左右端点。如果有两条线段相交，且不是一条线段完全属于另一条，这两个线段代表的顶点之间就会有一条边。问你最后生成的图是不是一颗树。
需要判断线段是否相交才能知道哪两个点之间有边，但是直接暴力判断肯定会超时。所以我们可以通过一些策略和stl的使用大大提升效率。
直接用pair存线段的左右端点然后sort，默认按照first也就是左端点从小到大排序。排序之后，从小到大遍历，一条边一条边的往里面加，我们用map，边存已经可以用的线段的右端点，边存这个线段代表的端点。每一次加入一条新的线段，在map中的key中查找是否存在大于新的线段的左端点的值。如果没有直接break，加入下一条边。找到之后判断这个值跟新加入的线段的右端点的值比较，如果大于，也直接break，因为在map中我们存的就是右端点的值。并且map默认是按照key的升序存储的，如果当前已经大了，后面的就都不需要判断了。如果出现了满足条件的，判断这两个点的父节点是否相同，如果已经相同了，还满足条件，再加上就会出现环，直接输出no即可。然后与这一条新加入的线段满足条件的所有线段都处理完之后，这条新线段的右端点以及代表的顶点存入map即可。如果最后还没有出现环，判断所有的点的父节点是不是一个即可。如果不是，直接输出NO。最后，如果还没有退出，就输出YES。

Code:

#include <bits/stdc++.h>
using namespace std;
#define pil    pair<int, int>
#define f      first
#define  s     second
const int     maxn = 1e6 + 10;
int           n, f[maxn];
pil           p[maxn];
map<int, int> pos;
int find(int x)
{
    return f[x] != x ? f[x] = find(f[x]) : x;
}
int main()
{
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> p[i].f >> p[i].s, f[i] = i;
    sort(p, p + n);
    for (int i = 0; i < n; i++)
    {
        int mid = p[i].f;
        while (true)
        {
            auto it = pos.upper_bound(mid);
            if (it == pos.end() || it->f > p[i].s)
                break;
            int p = i, q = it->s;
            if (find(p) == find(q))
            {
                cout << "NO\n";
                return 0;
            }
            mid        = it->f;
            f[find(p)] = find(q);
        }
        pos[p[i].s] = i;
    }
    for (int i = 0; i < n; i++)
    {
        if (find(i) != find(0))
        {
            cout << "NO\n";
            return 0;
        }
    }
    cout << "YES\n";
    return 0;
}
赏