p*****2
发帖数: 21240 | 1 下个月的任务做的差不多了，先上一题。
一个平面里边有很多点，由(x,y)来表示。
如果两个点在水平一条线上，或者在垂直一条线上，则可以相连。但是绝对不能斜线相
连。
比如 (2,3) (2,5)可以相连， (2,3) (5,3) 可以相连， 但是(2,3) (4,5)则不能相连。
为了把两个不能相连的点连起来则需要另外多加一个点才能做到。比如加入(2,5)则可
以把(2,3) (4,5)相连。
现在有很多个点，问最少需要加入多少个点，使得可以把所有的点连在一起。 | w****x
发帖数: 2483 | | l*****a
发帖数: 14598 | 3 大牛我觉得你从未离开
连。
【在 p*****2 的大作中提到】
: 下个月的任务做的差不多了，先上一题。
: 一个平面里边有很多点，由(x,y)来表示。
: 如果两个点在水平一条线上，或者在垂直一条线上，则可以相连。但是绝对不能斜线相
: 连。
: 比如 (2,3) (2,5)可以相连， (2,3) (5,3) 可以相连， 但是(2,3) (4,5)则不能相连。
: 为了把两个不能相连的点连起来则需要另外多加一个点才能做到。比如加入(2,5)则可
: 以把(2,3) (4,5)相连。
: 现在有很多个点，问最少需要加入多少个点，使得可以把所有的点连在一起。
| p*****2
发帖数: 21240 | 4
留点吧。不然下个月又得给加活了。这个月给加了不少。
【在 w****x 的大作中提到】
: 靠, 这个月把下个月做的差不多了...
| p*****2
发帖数: 21240 | 5
我两个月没怎么做题，现在都没感觉了。
【在 l*****a 的大作中提到】
: 大牛我觉得你从未离开
:
: 连。
| h****e
发帖数: 928 | | l*****a
发帖数: 14598 | 7 二野标准的BSO方式你还没领会到？
【在 w****x 的大作中提到】
: 靠, 这个月把下个月做的差不多了...
| A**l
发帖数: 2650 | 8 吐第一句话。。。
话说这题很简单吧，先横竖扫描去掉重复点，剩下n个点，需要n-1个点
连。
【在 p*****2 的大作中提到】
: 下个月的任务做的差不多了，先上一题。
: 一个平面里边有很多点，由(x,y)来表示。
: 如果两个点在水平一条线上，或者在垂直一条线上，则可以相连。但是绝对不能斜线相
: 连。
: 比如 (2,3) (2,5)可以相连， (2,3) (5,3) 可以相连， 但是(2,3) (4,5)则不能相连。
: 为了把两个不能相连的点连起来则需要另外多加一个点才能做到。比如加入(2,5)则可
: 以把(2,3) (4,5)相连。
: 现在有很多个点，问最少需要加入多少个点，使得可以把所有的点连在一起。
|
| p*****2
发帖数: 21240 | 9
每个点都可以走到其他的任何点，连接以后。
【在 A**l 的大作中提到】
: 吐第一句话。。。
: 话说这题很简单吧，先横竖扫描去掉重复点，剩下n个点，需要n-1个点
:
: 连。
| i***e
发帖数: 452 | | | | f*****e
发帖数: 2992 | 11 就是找n个联通分量，然后每个联通分量选个代表点连起来。
【在 A**l 的大作中提到】
: 吐第一句话。。。
: 话说这题很简单吧，先横竖扫描去掉重复点，剩下n个点，需要n-1个点
:
: 连。
| l****c
发帖数: 782 | 12 My method is that to use two hash_table to store the point_x and point_y.
When we could not find any same value in x_table or y_table, counter++ and
save the new value; When there is at least one same value in either table,
we don't need add counter.
However, I wonder how to use unordered_table more beautiful. Please give me
some suggestion.
int minNumofPoint(vector> point){
unordered_map hash_given_points_x;
unordered_map hash_given_points_y;
hash_given_points_x[point[0][0]] = 0;
hash_given_points_y[point[0][1]] = 0;
int counter = 0;
unordered_map::iterator it1;
unordered_map::iterator it2;
for (int i = 1; i
it1 = hash_given_points_x.find(point[i][0]);
it2 = hash_given_points_y.find(point[i][1]);
if (it1==hash_given_points_x.end()&&it2==hash_given_points_y.end()) {
counter++;
hash_given_points_x[point[i][0]] = 0;
hash_given_points_y[point[i][1]] = 0;
}
else if (it1==hash_given_points_x.end())
hash_given_points_x[point[i][0]] = 0;
else if (it2==hash_given_points_y.end())
hash_given_points_y[point[i][1]] = 0;
}
return counter;
} | p*****2
发帖数: 21240 | 13
me
不好意思，不太会看C＋＋代码。感觉逻辑有点问题吗？
比如 （2,3) counter=0
(1,4) counter =1
(2,4) counter=1
但实际上，这个时候counter=0吧？
【在 l****c 的大作中提到】
: My method is that to use two hash_table to store the point_x and point_y.
: When we could not find any same value in x_table or y_table, counter++ and
: save the new value; When there is at least one same value in either table,
: we don't need add counter.
: However, I wonder how to use unordered_table more beautiful. Please give me
: some suggestion.
: int minNumofPoint(vector> point){
: unordered_map hash_given_points_x;
: unordered_map hash_given_points_y;
: hash_given_points_x[point[0][0]] = 0;
| l****c
发帖数: 782 | 14 嗯，确实，之前第一次还想到这个问题，第二次给忘了。
再建一个hash for crossing point, 如果已经存在这个点counter--？
【在 p*****2 的大作中提到】
:
: me
: 不好意思，不太会看C＋＋代码。感觉逻辑有点问题吗？
: 比如 （2,3) counter=0
: (1,4) counter =1
: (2,4) counter=1
: 但实际上，这个时候counter=0吧？
| p*****2
发帖数: 21240 | 15
我是用dfs做的。
【在 l****c 的大作中提到】
: 嗯，确实，之前第一次还想到这个问题，第二次给忘了。
: 再建一个hash for crossing point, 如果已经存在这个点counter--？
| l****c
发帖数: 782 | 16 能展开说一下吗？
【在 p*****2 的大作中提到】
:
: 我是用dfs做的。
| p*****2
发帖数: 21240 | 17
void dfs(int[] x, int[] y, int[] g, int start, int group)
{
if(g[start]>0)
return;
g[start]=group;
for(int i=0;i
if(x[i]==x[start] || y[i]==y[start])
dfs(x,y,g,i,group);
}
int[] x=new int[n];
int[] y=new int[n];
for(int i=0;i
{
x[i]=in.nextInt();
y[i]=in.nextInt();
}
int[] g=new int[n];
int group=0;
for(int i=0;i
if(g[i]==0)
{
group++;
dfs(x,y,g,i,group);
}
out.println(group-1);
【在 l****c 的大作中提到】
: 能展开说一下吗？
| i***h
发帖数: 12655 | 18 这个应该是正解
【在 f*****e 的大作中提到】
: 就是找n个联通分量，然后每个联通分量选个代表点连起来。
| l*********u
发帖数: 19053 | 19 俺不会算法哈。
先把x或y等值的点去掉，省下n个点，要加n／２个点。３.５算４个点。
连。
【在 p*****2 的大作中提到】
: 下个月的任务做的差不多了，先上一题。
: 一个平面里边有很多点，由(x,y)来表示。
: 如果两个点在水平一条线上，或者在垂直一条线上，则可以相连。但是绝对不能斜线相
: 连。
: 比如 (2,3) (2,5)可以相连， (2,3) (5,3) 可以相连， 但是(2,3) (4,5)则不能相连。
: 为了把两个不能相连的点连起来则需要另外多加一个点才能做到。比如加入(2,5)则可
: 以把(2,3) (4,5)相连。
: 现在有很多个点，问最少需要加入多少个点，使得可以把所有的点连在一起。
|
|
