vijos1697 平面几何

给定N条直线、M组位置关系(平行或垂直)和Q个查询，要求输出共有多少组平行线，并回答询问的直线之间的位置关系。

提示：种类并查集。

#include <bits/stdc++.h>
using i64 = long long;

struct DSU {
    std::vector<int> f;
    DSU(int n) {
        init(n);
    }
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
    }
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    void join(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            f[y] = x;
        }
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

void solve() {
    int N, M, Q;
    std::cin >> N >> M >> Q;
    bool ok = true;
    DSU dsu(2*N);
    for (int i = 0; i < M; i++) {
        std::string a, b, c;
        std::cin >> a >> b >> c;
        int u = std::stoi(a.substr(1));
        int v = std::stoi(c.substr(1));
        u--, v--;
        if (b == "p") {
            if (dsu.same(u, v+N)) {
                ok = false;
                continue;
            }
            dsu.join(u, v);
            dsu.join(u+N, v+N);
        } else {
            if (dsu.same(u, v)) {
                ok = false;
                continue;
            }
            dsu.join(u, v+N);
            dsu.join(u+N, v);
        }
    }
    if (!ok) {
        std::cout << "There must be something wrong...\n";
        return;
    }
    std::map<int,int> cnt;
    for (int i = 0; i < N; i++) {
        int f = dsu.find(i);
        cnt[f] += 1;
    }
    int ans = 0;
    for (auto &kv : cnt) {
        ans += kv.second * (kv.second - 1) / 2;
    }
    std::cout << ans << "\n";
    for (int i = 0; i < Q; i++) {
        std::string a, b;
        std::cin >> a >> b;
        int u = std::stoi(a.substr(1));
        int v = std::stoi(b.substr(1));
        u--, v--;
        if (dsu.same(u, v)) {
            std::cout << "Parallel.\n";
        } else if (dsu.same(u, v+N)) {
            std::cout << "Vertical.\n";
        } else {
            std::cout << "No idea.\n";
        }
    }
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while (t--) solve();
    return 0;
}