문제 C 스키

질문 C: 스키
데 이 비 드 는 스키 초보 자 였 다. 그 는 활주 과정 에서 방향 을 조절 하 는 법 을 배우 지 못 했 고 어떻게 멈 추 는 지도 몰 랐 다.그래서 그의 활주 방식 은 높 은 눈 더미 에서 북쪽, 동쪽, 남쪽 또는 서쪽 으로 이동 하 는 방향 을 잘 조정 한 다음 에 직선 으로 미끄러져 서 다른 눈 더미 밑 에 계속 미끄러져 야 멈 출 수 있다.
그 는 이런 방식 으로 어떤 눈 더미 가 그 가 도착 할 수 없다 는 것 을 깨 달 았 다.그래서 그 는 지금 기 존의 눈 더 미 를 바탕 으로 자신 이 인위적으로 눈 더 미 를 늘 려 서 그 가 어떤 눈 더미 에서 다른 어떤 눈 더미 로 옮 길 수 있 도록 하려 고 한다.그 는 그 에 게 만들어 야 할 눈 더미 의 최소 수량 을 찾 아 달라 고 부탁 했다.
우 리 는 David 가 정수 좌표 에 만 눈 더 미 를 쌓 을 수 있다 고 가정 합 니 다.
입력:
입력 한 첫 줄 은 정수 n (1 ≤ n ≤ 100) 을 포함 하여 기 존의 눈 더미 수량 을 표시 합 니 다.다음 n 줄 의 각 줄 에는 두 개의 정수 Xi 와 Yi (1 ≤ Xi, Yi ≤ 1000) 가 포함 되 어 있 으 며, 기 존의 i 번 째 눈 더미 의 좌 표를 표시 합 니 다.북쪽 방향 은 Oy 축 방향 과 일치 하기 때문에 동쪽 방향 은 Ox 축 방향 과 일치 합 니 다.모든 눈 더미 의 위 치 는 다르다.
출력:
데 이 비 드 가 어떤 눈 더미 에서 다른 눈 더미 에 도달 할 수 있 도록 출력 하기 위해 만들어 야 할 최소 눈 더미 수 입 니 다.
샘플 입력:
2 2 1 1 2
샘플 출력:
1
문제 소개
초보 자 는 처음에는 생각 이 없 었 다. 여기 서 조 사장 이 생각 을 해 준 것 에 감사 했다.
이 스키 문제 에 대해 당신 은 이렇게 생각해 야 합 니 다. 두 개의 눈 더미 (여 기 는 모두 동행 하지 않 고 서로 다른 열 의 눈 더 미 를 말 합 니 다) 는 몇 개의 눈 더 미 를 새로 추가 하여 이 두 개의 눈 더 미 를 연결 시 켜 야 합 니 다. 당연히 하나, 세 개의 눈 더 미 를 말 합 니까?답 은 두 개다.
그래서 n 개 (동행 하지 않 고 다른 열) 눈 더미 에 n - 1 개의 새로운 눈 더 미 를 추가 해 야 합 니 다. 그러나 제목 이 그렇게 많은 눈 더 미 를 주 는 것 이 모두 동행 하지 않 고 다른 열 에 있 는 것 도 아 닙 니 다. 여기 서 우 리 는 처음부터 연 결 된 몇 개의 눈 더 미 를 하나의 눈 더미 로 보고 제목 이 준 데 이 터 는 m 개의 동행 하지 않 고 다른 열 에 있 는 눈 더 미 를 얻 을 수 있 습 니 다.그럼 마지막 으로 m - 1 개의 새 눈 더 미 를 추가 하면 됩 니 다.
코드

#include
using namespace std;

struct node
{
     
    int x,y;
};

node s[1001][1001];//    ，           
node s1[100];//         ，    
node set[100];//           ，    

node find(int x,int y)
{
     
    node temp;
    while(s[x][y].x!=x||s[x][y].y!=y)
    {
     
        int temp=x;
        x=s[x][y].x;
        y=s[temp][y].y;
    }
    temp.x=x,temp.y=y;
    return temp;
}

bool judge(node a,node b)
{
     
    return (a.x==b.x||a.y==b.y)?true:false;
}

int main()
{
     
    int n,sum=0;
    cin >> n;
    for(int i=0;i<n;i++)
    {
     
        int x,y;
        cin >> x >> y;
        s[x][y].x=x,s[x][y].y=y;
        s1[i].x=x,s1[i].y=y;
    }
    for(int k=0;k<n;k++)
    {
     
        for(int j=0;j<n;j++)
        {
     
            if(judge(s1[k],s1[j]))
            {
     
                node ap=find(s1[k].x,s1[k].y);
                node bp=find(s1[j].x,s1[j].y);
                if(ap.x==bp.x&&ap.y==bp.y)
                    continue;
                else
                {
     
                    s[ap.x][ap.y].x=bp.x;
                    s[ap.x][ap.y].y=bp.y;
                }
            }
        }
    }
    for(int i=0;i<n;i++)
    {
     
        node temp=find(s1[i].x,s1[i].y);
        bool key=true;
        for(int k=0;k<sum;k++)
            if(temp.x==set[k].x&&temp.y==set[k].y)key=false;
        if(key)
        {
     
            set[sum].x=temp.x,set[sum].y=temp.y;
            sum++;
        }
    }
    cout << sum-1;
    return 0;
}

업데이트
간소화판

#include 
using namespace std;
int parent[101];
struct node
{
     
    int x, y;
};

int getparent(int x)
{
     
    if (parent[x] == x)
        return x;
    parent[x] = getparent(parent[x]);
    return parent[x];
}

int main()
{
     
    int n;
    cin >> n;
    for (int i = 0; i <= n; ++i)
        parent[i] = i;
    int ans = 0;
    node* point = new node[n];
    for (int i = 0; i < n; ++i)
        cin >> point[i].x >> point[i].y;
    for (int i = 0; i < n; ++i) {
     
        for (int j = i + 1; j < n; ++j){
     
            if (point[i].x == point[j].x || point[i].y == point[j].y){
     
                int px = getparent(i);
                int py = getparent(j);
                if (px != py){
     
                    ans++;
                    parent[py] = px;
                }
            }
        }
    }
    cout << n - 1 - ans << endl;
    return 0;
}