【 템 플 릿 】 을 수집 합 니 다.
제목.
낙 곡 P3367 합병
해제
검색 집합 은 통합 과 조 회 를 지원 하 는 데이터 구조 입 니 다.합병: 원소 a, b 가 있 는 두 개의 집합 을 합병 하려 면 a 가 있 는 집합의 뿌리 노드 를 b 가 있 는 집합의 뿌리 노드 의 하위 노드 로 한다.한 나무의 모든 노드 는 같은 집합 에 속 하고 뿌리 노드 는 특별한 의미 가 없 으 며 단지 이 집합 을 대표 할 뿐이다.조회: 어떤 요소 가 어느 집합 에 있 는 지 알 고 싶 으 면 루트 노드 까지 부모 노드 를 계속 방문 합 니 다.
[최적화 방법] 경로 압축: 조회 과정 에서 가 는 노드 의 부모 노드 를 모두 루트 노드 로 바 꾸 고 나중에 조회 하 는 시간 을 줄인다.순위 에 따라 합병: 작은 나무의 깊이 를 최대한 줄 여 조회 속 도 를 빠르게 합 니 다.그러나 경로 압축 의 전제 에서 이 최적화 효 과 는 뚜렷 하지 않다.깊이 가 작은 수 를 깊이 가 큰 나무 에 합쳐서 합 친 수의 깊이 를 작 게 합 니 다.또한 깊이 를 집합 내의 원소 개수 로 바 꾸 어 더욱 편리 하고 실 용적 일 수 있다.현재 x 개의 요 소 를 집합 한다 고 가정 하면 뿌리 노드 의 부모 노드 를 - x 로 설정 합 니 다.
코드
#include
using namespace std;
const int maxn=1e4+5;
int n,m;
int fa[maxn];
int find(int x) {return fa[x]>0 ? fa[x]=find(fa[x]) : x;} // x
inline void unite(int r1,int r2) //
{
fa[r1]>fa[r2] ? fa[r2]+=fa[r1],fa[r1]=r2 : (fa[r1]+=fa[r2],fa[r2]=r1);
} // ，
int main()
{
memset(fa,-1,sizeof(fa));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int t,x,y; scanf("%d%d%d",&t,&x,&y);
int r1=find(x),r2=find(y);
if(t==1) {if(r1!=r2) unite(r1,r2);}
else if(r1==r2) printf("Y
");
else printf("N
");
}
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
