실제 문제 에서 의 응용 을 조사 하 다.

그리고 집합: 원 소 를 효율적으로 나 누고 구분 하 는 데 사용 합 니 다.
제목 출처: codeforces 1012 B
원래 문 제 는 다음 과 같다. 한 (n * m) 의 table 에서 element 는 부가 가치 행 위 를 할 것 이다. 만약 에 세 가지 물질 이 특정한 사각형 의 세 가지 정점 에 있 으 면 네 번 째 정점 에서 하나의 element 가 자동 으로 부가 가치 가 생 길 것 이다.현재 table 에 일부 물질 이 존재 합 니 다. 최소한 얼마나 많은 추가 물질 이 필요 한 지 구 해서 table 을 덮어 쓸 수 있 습 니 다.
이 문 제 를 푸 는 데 있어 서 유연 한 전환 사상 은 매우 중요 하 다.먼저 우 리 는 한 사각형 에 두 개의 인접 한 변 이 가득 덮 여 있 으 면 이 사각형 은 부가 가치 로 스스로 덮 을 수 있다 는 것 을 증명 할 수 있다.더 나 아가 우 리 는 이 두 변 을 수직 방향 으로 '분산' 한 후에 사각형 에 분산 시 키 면 여전히 부가 가 치 를 완성 할 수 있다 는 것 을 알 수 있다.
이 성질 의 본질은 무엇 입 니까? 세 개의 점 (r1, c1), (r1, c2), (r2, c1) 이 존재 하 는 것 을 (r1, c1), (r1, c2), (r2, c1) 세 쌍 의 값 사이 에 관계 가 있 기 때문에 r2 와 c2 도 관계 가 생 겼 습 니 다. 그래서 점 (r2, c2) 도 이에 따라 존재 하기 때문에 집합 으로 문 제 를 해결 할 수 있 습 니 다. 전집 은 (r1, r2... rn, c1, c2... cn) 입 니 다.
한 점 을 입력 할 때마다 두 값 유닛 에 대응 합 니 다.입력 이 완료 되면 약간의 집합 이 나타 납 니 다.이러한 집합 내부 의 가로 좌표 값 을 자 유 롭 게 조합 하여 형 성 된 점 은 이미 존재 하 는 것 이다.집합 간 에 조합 할 수 있 는 점 은 모두 아직 색칠 을 하지 않 았 다.최종 적 으로 우리 가 원 하 는 효 과 는 모든 값 이 하나의 집합 에 있다 는 것 이다. 그러면 어느 점 을 검사 하 든 그의 가로 좌 표 는 반드시 연 결 된 것 이다.따라서 우리 가 추가 로 점 을 바 르 는 역할 은 실제로 서로 다른 집합 을 연결 시 키 는 것 이기 때문에 결 과 는 집합 수 - 1 과 같다.
AC 코드 첨부
 

#include
#include
using namespace std;

int p[400010],r[400010];

int fa(int ch)
{
    if(p[ch]==ch)
        return ch;
    return fa(p[ch]);
}

void unite(int u,int v)
{
    int fu=fa(u);
    int fv=fa(v);
    if(fu!=fv)
    {
        if(r[fv]==r[fu])
        {
            r[fu]++;
            p[fv]=fu;
        }
        else if(r[fu]>n>>m>>q;
    for(int i=1; i<=n+m; i++)
        p[i]=i;
    for(int i=0; i