마늘 손님 접 룡 (띠 권 및 템 플 릿 문제 수집)
1323 단어 데이터 구조
제목 대의: 일련의 합병 조작 을 통 해 두 점 사이 의 거 리 를 구한다.
제목 사고방식: 우 리 는 두 장의 카드 가 같은 대열 에 있 는 지 아 닌 지 를 쉽게 통계 하고 집합 을 찾 으 면 된다.관건 은 어떻게 계산 하 느 냐 하 는 것 이다. 한 대열 에 있 는 두 개의 카드 사이 의 카드 수 는 각 카드 에서 대열 머리 까지 의 카드 수 를 유지 하면 된다.같은 대열 에 있 는 두 개의 카드 사이 의 카드 수 를 계산 할 때, 두 개의 카드 를 대열 머리 까지 의 카드 수 를 차이 나 게 하면 된다.
배 운 것: 가중 및 수집.
코드:
// ，
#include
using namespace std;
const int maxn=5e6+2;
int pre[maxn];
int val[maxn];//
int Size[maxn];//
void build(int n)
{
for(int i=0;i<=n;i++)
pre[i]=i,val[i]=0,Size[i]=1;
}
int find(int x)
{
if(pre[x]==x) return x;
int y=pre[x];
pre[x]=find(y);
val[x]+=val[y];//x
return pre[x];
}
bool join(int x,int y)
{
int p=find(x);
int q=find(y);
if(p!=q){
pre[p]=q;
//val[q]+=val[p];
val[p]=Size[q];//p ， q
Size[q]+=Size[p];//q ，p
return true;
}
return false;
}
int main()
{
int n;scanf("%d",&n);
build(n);
while(n--){
char c;
int x,y;
cin>>c>>x>>y;
if(c=='M'){
join(x,y);
}
else{
if(find(x)!=find(y)) cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
