【练习】任意点

任意点

https://ac.nowcoder.com/acm/problem/15808

题目

题目描述：
平面上有若干个点，从每个点出发，你可以往东南西北任意方向走，直到碰到另一个点，然后才可以改变方向。

请问至少需要加多少个点，使得点对之间互相可以到达。

输入描述：
第一行一个整数n表示点数（ 1 <= n <= 100)。
第二行n行，每行两个整数xi, yi表示坐标（ 1 <= xi, yi <= 1000)。
y轴正方向为北，x轴正方形为东。

输出描述：

输出一个整数表示最少需要加的点的数目。

解析

1）知识点

一道简单的并查集，把我搞了好久，一开始的写法还是不知道为啥错了QAQ

2）看题目

这道题简答来说就是，某一个点可以到达同行同列任何一个点，求至少要加多少个点可以让所有点可以互相到达。

3）算法分析

题目很清晰了，同行同列的就是同一个集合里面的。也就是求出这样的连通块的数量，减一输出就好了
（因为两个连通块之间只要一个点相连就可以了）。
我一开始想的是，我们先建立一个地图，然后进行二维的并查集，得到地图上每一个位置的父位置。每加入一个节点就将行列有点的位置全部合并。
最后在地图上面有点的位置，就看有几个节点的父亲是自己就好了。这就是连通块的数量。
但这样wa了，还wa的很惨。
然后我问了一下大佬才发现，其实可以直接把点列出来。给每一个点一个1~100的编号就行了（点用pair保存x和y值）。
然后进行一个二重循环，如果两个点行相同或者列相同就合并就好了。
最后也是求出有几个点的父亲是自己。

4）算法操作

操作的话首先是给每个点进行父亲设置为自己的初始化：
```
for (int i = 1; i <= n; i++)
    fa[i] = i;
```

然后就是输入每个点的相关数据（x，y的值）：

for (int i = 1; i <= n; i++)
    cin >> info[i].first >> info[i].second;

接下来就是双重循环遍历点对了：

int ans = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
        if (!mp[i][j]) continue;
        pair<int, int> x = make_pair(i, j);
        if (x == find(x))  ans++;
    }

如此而已。

5）打代码

所以就是先初始化父亲数组。
然后输入节点数据。
接下来遍历判断，输出值就好了。
下面全代码~

WA代码

#include <iostream>
#include <map>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e3 + 7;
int n;
int mp[MAX][MAX];
pair<int, int> fa[MAX][MAX];
//全局变量区

pair<int, int> find(pair<int, int> x);
void merge(pair<int, int> x, pair<int, int> y);
void add(int u, int v);
//函数预定义区

int main() {
    IOS;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            fa[i][j] = make_pair(i, j);
        }
    }
    for (int i = 1; i <= n; i++) {
        int x, y; cin >> x >> y;
        mp[x][y] = 1;
        add(x, y);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (!mp[i][j]) continue;
            pair<int, int> x = make_pair(i, j);
            if (x == find(x)) {
                ans++;
            }
        }
    }
    cout << ans - 1 << endl;
    return 0;
}
pair<int, int> find(pair<int, int> x) {
    pair<int, int>& t = fa[x.first][x.second];
    return x == t ? x : t = fi***oid merge(pair<int, int> x, pair<int, int> y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        fa[x.first][x.second] = y;
    }
}
void add(int u, int v) {
    for (int i = 1; i <= n; i++) 
        if (mp[i][v]) 
            merge(make_pair(u, v), make_pair(i, v));
    for (int i = 1; i <= n; i++)
        if (mp[u][i]) 
            merge(make_pair(u, v), make_pair(u, i));
}

AC代码

#include <iostream>
#include <map>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e2 + 7;
int n;
int fa[MAX];
pair<int, int> info[MAX];
//全局变量区

int find(int x);
void merge(int x, int y);
//函数预定义区

int main() {
    IOS;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    for (int i = 1; i <= n; i++) {
        cin >> info[i].first >> info[i].second;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (info[i].first == info[j].first || info[i].second == info[j].second)
                merge(i, j);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (i == find(i)) {
            ans++;
        }
    }
    cout << ans - 1 << endl;
    return 0;
}
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        fa[x] = y;
    }
}

牛客算法竞赛入门课题解文章被收录于专栏

憨憨的专栏