데이터 구조 5 - 4 - 1 및 검색 집합
그리고 집합 은 본질 적 으로 나무 에 대한 지식 을 이용 하 는 것 이다. 집합 과 관련 된 표현 에 자주 사용 되 는데 일반적인 이 진 트 리 와 다 르 고 집합 은 부모 노드 를 가리 키 는 지침 으로 분류 하기 쉽 고 서브 노드 를 찾기 어렵다.
코드 구현
간단 한 병합 집합 은 주로 세 개의 함수 가 있 는데 초기 화, 합병, 조회 가 있 습 니 다.
초기 화 에는 여러 가지 방법 이 있다.모두 자신 으로 초기 화 할 수 있 습 니 다. 시작 상태 에서 모든 노드 가 하나의 나무 라 고 생각 하 는 것 과 같 습 니 다. 이 나무 들 은 하나의 노드 만 있 고 자신 을 가리 키 게 합 니 다.모두 초기 화 할 수도 있 습 니 다. - 1. 이런 초기 화 는 맨 위 에 있 는 노드 에 이 집합 이 몇 개의 노드 가 있 는 지 저장 할 수 있 는 장점 이 있 습 니 다.
void init()
{
for(int i=1;i<=n;i++)
data[i]=i;
}
//
void init()
{
for(int i=1;i<=n;i++)
data[i]=-1;
}
// -1
합병 은 초기 화 방식 에 따라 미세한 차이 도 있 지만 주요 한 사고방식 은 모두 같다. 두 노드 가 한 집합 에 있 는 지 비교 하고 없 으 면 합병 할 수 있다 는 것 을 설명 한다. 함수 찾기 로 집합의 뿌리 노드 를 찾 은 다음 에 한 노드 가 다른 노드 를 가리 키 면 합병 작업 을 완성 할 수 있다.
void merge(int x,int y)
{
int tx=find(x);
int ty=find(y);
if(tx!=ty)
data[tx]=data[ty];
// -1 data[ty]+=data[tx]，
}
검색 은 초기 화 에 따라 검색 종료 표 지 를 설정 해 야 합 니 다.초기 화 를 사용 할 때 끝 난 플래그 를 찾 는 것 은 해당 위치 값 이 자신의 아래 표 시 됩 니 다.- 1 로 초기 화 할 때 끝 난 플래그 를 찾 는 것 은 해당 위치 값 이 0 보다 적 습 니 다.
int find(int x)
{
while(data[x]!=x)
x=data[x];
return x;
}
//
int find(int x)
{
while(data[x]>=0)
x=data[x];
return x;
}
int find(int n)
{
if(pre[n]==n)
return n;
else
return pre[n]=find(pre[n]);
}
//
그리고 조사 집 자체 가 어렵 지 않 습 니 다. 앞에서 블 루 브리지 ACM 을 할 때 선배 들 은 어렵 지 않다 고 했 습 니 다. 위로 찾 는 과정 을 잘 이해 하면 됩 니 다.전체 코드 는 다음 과 같다.
#include
",find(choice));
scanf("%d",&choice);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Sparse Table을 아십니까? 나는 알고 있다.Sparse Table을 지금 배웠으므로, 메모를 겸해 씁니다. 불변의 수열의 임의의 구간에 대한 최소치/최대치를, 전처리 $O(N\log N)$, 쿼리 마다 $O(1)$ 로 구하는 데이터 구조입니다. 숫자 열의 값...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
