URAL 1966 Cycling Roads - 並查集 + 線段相交判斷

問題描述

平面上有 n 個點 (n ≤ 200)，m 條邊 (m < n)，每條邊連接兩點。若兩條邊真相交 (非端點相交)，則其四個端點視為連通。問所有點是否連通 (即並查集中只有一個集合且大小為 n)。

算法流程

1. 初始化並查集：每點自成集合。
2. 處理邊：讀入邊 (u, v)，合併 u, v。同時檢查是否有其他點在線段 uv 上 (共線且在範圍內)，若有則合併。
3. 檢查邊對相交：雙重循環枚舉所有邊對 (i, j)，判斷線段 (u_i, v_i) 和 (u_j, v_j) 是否真相交 (內部點相交)。若相交，合併四端點 (實際只需合併任意一對，如 u_i 和 u_j，因各自已與對應端點合併)。
4. 判斷連通性：檢查並查集中根的個數，或檢查 size[find(1)] == n。

幾何判斷：線段真相交

向量叉積法：

struct Point { double x, y; };
Point operator-(Point a, Point b) { return {a.x-b.x, a.y-b.y}; }
double cross(Point a, Point b) { return a.x*b.y - a.y*b.x; }
int dcmp(double x) { const double EPS=1e-8; return (x>EPS)-(x<-EPS); }

bool proper_intersect(Point a1, Point a2, Point b1, Point b2) {
    double c1 = cross(a2-a1, b1-a1);
    double c2 = cross(a2-a1, b2-a1);
    double c3 = cross(b2-b1, a1-b1);
    double c4 = cross(b2-b1, a2-b1);
    return dcmp(c1)*dcmp(c2) < 0 && dcmp(c3)*dcmp(c4) < 0;
}

注意：端點相交、共線重疊不算「真相交」，題目要求內部點相交。上述叉積異號條件恰好排除了端點情況。

點在線段上判斷 (處理邊讀入時)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 210;
const double EPS = 1e-8;

struct Point { double x, y; } p[MAXN];
int n, m;
int fa[MAXN], sz[MAXN];
int u[MAXN], v[MAXN];

Point operator-(Point a, Point b) { return {a.x-b.x, a.y-b.y}; }
double cross(Point a, Point b) { return a.x*b.y - a.y*b.x; }
double dot(Point a, Point b) { return a.x*b.x + a.y*b.y; }
int dcmp(double x) { return (x>EPS) - (x<-EPS); }

bool proper_intersect(Point a1, Point a2, Point b1, Point b2) {
    double c1 = cross(a2-a1, b1-a1);
    double c2 = cross(a2-a1, b2-a1);
    double c3 = cross(b2-b1, a1-b1);
    double c4 = cross(b2-b1, a2-b1);
    return dcmp(c1)*dcmp(c2) < 0 && dcmp(c3)*dcmp(c4) < 0;
}

bool on_segment(Point p, Point a, Point b) {
    return dcmp(cross(a-p, b-p)) == 0 && dcmp(dot(a-p, b-p)) < 0;
}

int find(int x) { return fa[x]==x ? x : fa[x]=find(fa[x]); }
void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x != y) { fa[y] = x; sz[x] += sz[y]; }
}

int main() {
    while (scanf("%d%d", &n, &m) == 2) {
        for (int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
        for (int i = 1; i <= n; i++) { fa[i] = i; sz[i] = 1; }
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &u[i], &v[i]);
            unite(u[i], v[i]);
            // 檢查點在線段上
            for (int j = 1; j <= n; j++)
                if (j != u[i] && j != v[i] && on_segment(p[j], p[u[i]], p[v[i]]))
                    unite(j, u[i]);
        }
        // 邊對相交
        for (int i = 0; i < m; i++)
            for (int j = i+1; j < m; j++)
                if (proper_intersect(p[u[i]], p[v[i]], p[u[j]], p[v[j]]))
                    unite(u[i], u[j]);
        puts(sz[find(1)] == n ? "YES" : "NO");
    }
    return 0;
}

複雜度

• 讀入 + 點在線段檢查：O(m·n) ≤ 4萬
• 邊對相交檢查：O(m²) ≤ 4萬
• 並查集操作近似 O(1)
• 總體極快，n=200 完全夠用。