题目
题目描述:平面上有若干个点,从每个点出发,你可以往东南西北任意方向走,直到碰到另一个点,然后才可以改变方向。
请问至少需要加多少个点,使得点对之间互相可以到达。
第一行一个整数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; } }