도전 프로 그래 밍 (알고리즘 과 데이터 구조) - 고등 데이터 구조

상호 질의 집합
제목 14.1 Disjoint Set: Union Find Tree 를 연결 하 는 사 고 는 주로 수집 하 는 사상 을 사용 했다.관련 설명 링크 는 매우 재 미 있 고 상세 한 설명 을 수집 합 니 다.

첫 번 째 방법 은 링크 안의 간단 한 데이터 구 조 를 사 용 했 고 pre [i] 배열 로 i 의 상급 을 기록 했다. i = pre [i] 는 i 가 바로 뿌리 노드 이다.

#include 
#include 
using namespace std;

const int Max = 10005;
int pre[Max];
int n, q, com, x, y;

int findRoot(int x)
{
    int r = x;
    while(pre[r]!=r)//    
    {
        r = pre[r];
    }
    int j = x, i;
    while(pre[j]!=r)//    ，             
    {
        i = j;
        pre[j] = r;
        j = pre[i];
    }
    return r;
}

void join(int x, int y)
{
    int fx = findRoot(x), fy = findRoot(y);
    if(fx!=fy)//    
    {
        pre[fx] = fy;
    }
}
int main()
{
    scanf("%d %d", &n, &q);
    for(int i=0; i

두 번 째 는 책 에 있 는 방법 으로 하나의 데이터 구조 인 Disjoint Set 를 직접 정 의 했 는데 이것 은 상호 집합 (하나의 요소 가 여러 집합 에 동시에 포함 되 지 않 는 집합) 으로 데 이 터 를 분류 관리 하 는 데이터 구조 이다. ， ， ， 。 이런 사상 은 Kruskal 에 최소 생 성 트 리 를 만 드 는 데 사용 할 수 있다.이런 데이터 구 조 는 다음 과 같은 조작 이 있다.

조작 함수
속뜻
makeSet(x)
요소 x 만 포함 하 는 새 집합 만 들 기
findSet(x)
x 요소 의 집합 을 포함 하 는 '대표' 요 소 를 구하 십시오.
unite(x, y)
지정 한 요소 x, y 통합
same(x,y)
x 와 y 가 같은 집합 에 있 는 지 여 부 를 판단 하면 1 로 돌아 가 고 그렇지 않 으 면 0 으로 돌아간다.
다음 코드 에 정 의 된 DisjointSet 클래스 는 템 플 릿 라 이브 러 리 로 기록 되 어 나중에 직접 사용 할 수 있 습 니 다.그 복잡 도 는 O (log (N) 보다 낮다.

#include 
#include 
#include 
using namespace std;

int n, q, com, x, y;

class DisjointSet
{
    public:
        vector rank, p;//rank      ，rank[x]， x    ，p     

    DisjointSet(){}
    DisjointSet(int size)
    {
        rank.resize(size, 0);
        p.resize(size, 0);
        for(int i=0; irank[y])//             
        {
            p[y] = x;
        }
        else
        {
            p[x] = y;
            if(rank[x]==rank[y])
            {
                rank[y]++;
            }
        }
    }

    int findSet(int x)//  x     
    {
        if(x!=p[x])
        {
            p[x] = findSet(p[x]);
        }
        return p[x];
    }

};
int main()
{
    scanf("%d %d", &n, &q);

    DisjointSet ds = DisjointSet(n);

    for(int i=0; i

KD Tree
k - d 트 리 (k - dimensional 트 리 의 약칭) 는 k 차원 데이터 공간 을 분할 하 는 데이터 구조 이다.주로 다 차원 공간 핵심 데이터 검색 (예 를 들 어 범위 검색 과 최근 인접 검색) 에 사 용 됩 니 다.KD Tree 는 BST (이 진 검색 트 리) 가 다 차원 공간 에서 확장 되 는 것 입 니 다. 사실 높 은 차원 으로 확장 되 었 을 때 도 비슷 합 니 다. 여러 차원 만 고려 해 야 합 니 다. 가장 눈 에 띄 는 생각 은 각 층 에 대해 저 는 서로 다른 차원 의 수 치 를 key 로 비교 하 는 것 입 니 다.예 를 들 어 2 차원 데이터 에 대해 저 는 1 층 은 1 차원, 2 층 은 2 차원, 3 층 은 1 차원, 4 층 은 2 차원 을 사용 합 니 다. 이렇게 하면 나무 한 그루 가 비교적 고 르 게 세 울 수 있 습 니 다.

범위 검색 제목 14.2 링크 Range Search (kd Tree) 이 문 제 는 2 차원 범위 검색 입 니 다. 다음은 책 에 있 는 KD Tree 템 플 릿 입 니 다. 남 겨 두 었 다가 사용 합 니 다. find 는 범위 검색 입 니 다. MakeKDTree 는 구조 KD Tree 입 니 다.

#include 
#include 
#include 
#include 
using namespace std;

class Node//      
{
public:
    int location;//                
    int p, l, r;//   ，    ，    
    Node(){};
};

class Point//     
{
public:
    int id, x, y;//id         ,x,y   key 
    Point(){}
    Point(int id, int x, int y): id(id), x(x), y(y) {}//    Point(id, x, y)           
    bool operator < (const Point &p) const{//           
        return id ans;//    

//         ，    x，    y
bool lessX(const Point &p1, const Point &p2)
{
    return p1.x < p2.x;
}
bool lessY(const Point &p1, const Point &p2)
{
    return p1.y < p2.y;
}

int makeKDTree(int l, int r, int depth)//  KD Tree
{
    if(l==r) return NIL;
    int mid = (l+r)/2;
    int t = np++;
    if(depth%2==0)//   x,y  
        sort(P+l, P+r, lessX);
    else
        sort(P+l, P+r, lessY);
    //   
    T[t].location = mid;
    T[t].l = makeKDTree(l, mid, depth+1);
    T[t].r = makeKDTree(mid+1, r, depth+1);

    return t;
}

void find(int v, int sx, int tx, int sy, int ty, int depth, vector &ans)//          
{
    int x = P[T[v].location].x;
    int y = P[T[v].location].y;

    if(sx<=x && tx>=x && sy<=y && ty>=y)//        
    {
        ans.push_back(P[T[v].location]);
    }

    if(depth%2==0)
    {
        if(T[v].l!=NIL && sx<=x)//    
        {
            find(T[v].l, sx, tx, sy, ty, depth+1, ans);
        }
        if(T[v].r!=NIL && tx>=x)//    
        {
            find(T[v].r, sx, tx, sy, ty, depth+1, ans);
        }
    }
    else
    {
        if(T[v].l!=NIL && sy<=y)
        {
            find(T[v].l, sx, tx, sy, ty, depth+1, ans);
        }
        if(T[v].r!=NIL && ty>=y)
        {
            find(T[v].r, sx, tx, sy, ty, depth+1, ans);
        }
    }
}
int main()
{
    int x, y, q;
    scanf("%d", &N);
    for(int i=0; i

KNN 검색 제목 링크 The Closest M Points

먼저 다른 사람의 코드 를 붙 이 고 나중에 시간 이 있 으 면 스스로 연구 해 보 세 요.

#include
#define sq(x) (x)*(x)
#define N (55555)
 
using namespace std;
 
int idx,k,n,m,q;
 
struct Node
{
    int x[5];
    bool operator < (const Node &u) const
    {
        return x[idx] < u.x[idx];
    }
} P[N];
 
typedef pair PDN;
priority_queue que;
 
struct KD_Tree
{
    int sz[N<<2]; Node p[N<<2];
 
    void build(int i,int l,int r,int dep)
    {
        if (l>r) return;
        int mid=(l+r)>>1;
        idx=dep%k;sz[i]=r-l;
        sz[i<<1]=sz[i<<1|1]=-1;
        nth_element(P+l,P+mid,P+r+1);
        p[i]=P[mid];
        build(i<<1,l,mid-1,dep+1);
        build(i<<1|1,mid+1,r,dep+1);
    }
 
    void query(int i,int m,int dep,Node a)
    {
        if (sz[i]==-1) return;
        PDN tmp=PDN(0,p[i]);
        for(int j=0;j=p[i].x[dim]) swap(lc,rc);
        if (~sz[lc]) query(lc,m,dep+1,a);
        if (que.size()0;i--)
            {
                printf("%d",pp[i].x[0]);
                for(int j=1;j