CF1278D

胖头鱼学员 · 2020-09-23 00:15:47 · 题解

CF1278D

CF传送门

洛谷传送门

QuestionMeaning

给定n个区间[l_1, r_1]，[l_2, r_2]，……[l_n, r_n]（\forall i :i \in [1, n], l_i < r_i）。当且仅当两条线段i和j（\forall i, j \in [1, n]）有相交时，图上对应的i和j连接一条无向边。问你最后这张图是不是一棵树。

Solution

该方法的主要思想是求出线段相交的线性数。

用扫线法可以找到交叉点。我们将为开放段的端点维护一个集合。当我们添加一个线段时，我们会找到与它相交的所有线段，也就是说，所有比它早结束的线段。

显然，如果交叉口的数量大于{n - 1}，那么答案是否。所以一旦我们找到n个交叉点，我们就停止我们的算法。

之后，有必要检查结果图的连通性，可以使用DFS或DSU来执行此操作。

Code

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); i++)

typedef long long li;
typedef pair<li, li> pt;

const int N = 500010;

int n, cnt;
pt a[N];
vector<int> g[N];
bool used[N];

void dfs(int v, int p = -1) {
  used[v] = true;
  for (auto to : g[v]) {
    if (to != p) {
      if (!used[to]) {
        dfs(to, v);
      }
    }
  }
}

int main() {
  scanf("%d", &n);
  forn(i, n) scanf("%d%d", &a[i].x, &a[i].y);
  vector<pt> evs;
  forn(i, n) {
    evs.pb(mp(a[i].x, i));
    evs.pb(mp(a[i].y, i));
  }
  sort(all(evs));
  set<pt> cur;
  for (auto it : evs) {
    if (cnt >= n) {
      break;
    }
    if (cur.count(it)) {
      cur.erase(it);
    } else {
      int i = it.y;
      int r = a[i].y;
      for (auto jt : cur) {
        if (jt.x > r) {
          break;
        }
        int j = jt.y;
        g[i].pb(j);
        g[j].pb(i);
        cnt++;
        if (cnt >= n) {
          break;
        }
      }
      cur.insert(mp(a[i].y, i));
    }
  }
  dfs(0);
  puts(cnt == n - 1 && count(used, used + n, 1) == n ? "YES" : "NO");
}