1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102

#include <bits/stdc++.h>
using namespace std;
#define int long long

typedef long long ll;
typedef pair<ll, ll> pll;

// 전역 변수 선언이다.
int n;                              // 철판의 개수를 저장하는 변수이다.
vector<pll> plates;                 // 각 철판의 (s, t) 값을 저장하는 벡터이다.
vector<ll> comp;                    // 좌표 압축을 위한 s와 t 값들을 저장하는 벡터이다.
ll ans;                             // 최종 검의 길이를 저장할 변수이다.

int par[505050];                    // Union-Find에서 각 정점의 부모를 저장하는 배열이다.
ll mx[505050];                      // 각 그룹에서 최대값을 저장하는 배열이다.
ll sumVal[505050];                  // 각 그룹 내 정점들의 합을 저장하는 배열이다.
int cycle[505050];                  // 각 그룹에 사이클 존재 여부를 저장하는 배열이다.

// Union-Find 초기화 함수이다.
void initUnionFind(int size) {
    for (int i = 0; i < size; i++) {
        par[i] = i;               // 초기에는 자기 자신이 부모이다.
        mx[i] = comp[i];          // 초기에는 해당 정점의 값이 최대값이다.
        sumVal[i] = comp[i];      // 초기에는 해당 정점의 값이 그룹 합이다.
        cycle[i] = 0;             // 초기에는 사이클이 없다고 설정한다.
    }
}

// Union-Find의 find 함수이다. 경로 압축을 수행한다.
int findUF(int v) {
    return (v == par[v]) ? v : par[v] = findUF(par[v]);  // 부모를 재귀적으로 찾으며 경로 압축을 수행한다.
}

// 두 정점을 합치는 merge 함수이다.
// 이미 같은 그룹인 경우 false를 반환하고, 사이클 발생을 표시한다.
bool mergeUF(int u, int v) {
    u = findUF(u), v = findUF(v);
    if (u == v) return false;       // 이미 같은 그룹이면 합치지 않고 false를 반환한다.
    par[u] = v;                    // u의 부모를 v로 설정한다.
    mx[v] = max(mx[u], mx[v]);     // 그룹 v의 최대값을 갱신한다.
    sumVal[v] += sumVal[u];        // 그룹 v의 합을 갱신한다.
    cycle[v] = cycle[u] || cycle[v]; // 그룹 내 사이클 여부를 갱신한다.
    return true;                   // 합치기에 성공하면 true를 반환한다.
}

// 좌표 압축된 comp 벡터에서 값 x의 인덱스를 반환하는 함수이다.
int idx(ll x) {
    return lower_bound(comp.begin(), comp.end(), x) - comp.begin();
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 철판의 개수를 입력받는다.
    cin >> n;
    plates.resize(n);
    comp.reserve(n * 2);
    // 각 철판의 s와 t 값을 입력받으며 좌표 압축용 벡터에 추가한다.
    for (int i = 0; i < n; i++){
        cin >> plates[i].first >> plates[i].second;
        comp.push_back(plates[i].first);
        comp.push_back(plates[i].second);
    }
    // 좌표 압축을 위해 comp 벡터를 정렬하고 중복을 제거한다.
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());

    // comp 벡터의 크기만큼 Union-Find를 초기화한다.
    initUnionFind(comp.size());

    // 각 철판을 두 정점을 잇는 간선으로 보고, 해당 정점들을 Union-Find로 연결한다.
    for (int i = 0; i < n; i++){
        int u = idx(plates[i].first);
        int v = idx(plates[i].second);
        if (!mergeUF(u, v)) {       // 이미 같은 그룹인 경우라면 사이클 발생을 표시한다.
            cycle[findUF(u)] = 1;
        }
    }

    // 전체 철판의 s와 t 값의 합을 ans에 더한다.
    ans = 0;
    for (int i = 0; i < n; i++){
        ans += plates[i].first + plates[i].second;
    }

    // 각 좌표 압축된 값의 대표 그룹에 대해 손실 비용을 계산한다.
    // 그룹이 사이클이면 그룹 내 모든 값의 합이 손실 비용이다.
    // 그룹이 트리 구조이면 그룹 내 합에서 최대값을 뺀 값이 손실 비용이다.
    for (int i = 0; i < (int)comp.size(); i++){
        if (findUF(i) != i) continue;   // 대표 정점이 아니면 건너뛴다.
        if (cycle[i]) {
            ans -= sumVal[i];
        } else {
            ans -= (sumVal[i] - mx[i]);
        }
    }

    // 최종 검의 길이를 출력한다.
    cout << ans << "\n";
    return 0;
}