ACM LA 3644: X - Plosives (병렬 집합)

컴퓨터 과학 에서 집합 을 찾 는 것 은 트 리 형 데이터 구조 로 서로 교차 하지 않 는 집합 (Disjoint Sets) 의 합병 과 조회 문 제 를 처리 하 는 데 사용 된다.하나의 연합 - 검색 알고리즘 (union - find algorithm) 은 이 데이터 구조 에 작용 하 는 두 개의 동작 을 정의 합 니 다.
Find: 요소 가 어느 부분 에 속 하 는 지 확인 합 니 다.그것 은 두 요소 가 같은 부분 집합 에 속 하 는 지 확인 하 는 데 사 용 될 수 있다
유 니 온: 두 부분 집합 을 같은 집합 으로 합 칩 니 다
이 두 가지 조작 을 지원 하기 때문에 하나의 교차 하지 않 는 집합 도 연합 - 데이터 구조 찾기 (유 니 온 - find data structure) 또는 합병 - 집합 찾기 (merge - find set) 라 고 불 린 다.다른 중요 한 방법 은 MakeSet 입 니 다. 단일 요소 집합 을 만 드 는 데 사 용 됩 니 다.

#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 100005;

int f[maxn];

int find(int x)
{
    if (x == f[x]) return x;
    return f[x] = find(f[x]);
}

int main()
{
    int a, b;
    while (scanf ("%d", &a) != EOF){
        for (int i = 0; i < maxn; ++ i)
            f[i] = i;
        int ans = 0;
        while (a >= 0){
            scanf ("%d", &b);
            int t1 = find(a), t2 = find(b);
            if (t1 != t2) f[t1] = t2;
            else ++ ans;
            scanf ("%d", &a);
        }
        printf ("%d
", ans);
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

ACM - 계산 기하학 적 Pick - up sticks -- poj 2653

Description Stan has n sticks of various length. The data for each case start with 1 <= n <= 100000, the number of stick...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

ACM LA 3644: X - Plosives (병렬 집합)

좋은 웹페이지 즐겨찾기