13167번: 포스터

https://www.acmicpc.net/problem/13167

한 포스터가 다른 포스터를 가릴 수 있을 때, 각 포스터가 보이는 부분의 넓이를 구하는 문제이다.

포스터의 꼭지점 좌표를 압축하면 2n * 2n 격자 모양으로 만들 수 있다. 이렇게 만든 격자를 왼쪽에서부터 한 열씩 본다. 어떤 포스터의 세로 구간 내에 포스터가 붙지 않은 영역 넓이 계산 및 포스터를 붙임 체크는 Union-find 자료 구조로 빠르게 처리할 수 있다. 현재 보고 있는 열에서 가장 나중에 붙인 포스터부터 붙여 보며 각 포스터마다 보이는 영역 넓이를 누적시켜준다.

시간복잡도는 $O(n^2)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, sx[5000], sy[5000], ex[5000], ey[5000], p[10000], ix[10000], iy[10000];
long long res[5000];
int f(int x) { return x^p[x] ? p[x] = f(p[x]) : x; }
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d%d", sx + i, sy + i, ex + i, ey + i);
        ix[i] = sx[i]; ix[i + n] = ex[i];
        iy[i] = sy[i]; iy[i + n] = ey[i];
    }
    sort(ix, ix + 2 * n);
    sort(iy, iy + 2 * n);
    for (int i = 0; i < n; i++) {
        sx[i] = lower_bound(ix, ix + 2 * n, sx[i]) - ix;
        ex[i] = lower_bound(ix, ix + 2 * n, ex[i]) - ix;
        sy[i] = lower_bound(iy, iy + 2 * n, sy[i]) - iy;
        ey[i] = lower_bound(iy, iy + 2 * n, ey[i]) - iy;
    }
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < 2 * n; j++) p[j] = j;
        for (int j = n; j--;) if (sx[j] <= i && i < ex[j])
            for (int k = f(sy[j]); k < ey[j]; k = p[f(k)] = f(k + 1))
                res[j] += 1LL * (ix[i + 1] - ix[i])*(iy[k + 1] - iy[k]);
    }
    for (int i = 0; i < n; i++) printf("%lld\n", res[i]);
    return 0;
}

4195번: Virtual Friends

https://www.acmicpc.net/problem/4195

union-find를 이용해 친구 관계를 관리한다.

시간복잡도는 테스트 케이스마다 $O(f\lg f)$

#include<cstdio>
#include<string>
#include<map>
using namespace std;
int t, f, p[200001], sz[200001];
char a[21], b[21];
int par(int x) { return x^p[x] ? p[x] = par(p[x]) : x; }
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d", &f);
        map<string, int> mp;
        for (int i = 0, c = 0; i < f; i++) {
            scanf("%s%s", a, b);
            if (!mp[a]) mp[a] = ++c, p[c] = c, sz[c] = 1;
            if (!mp[b]) mp[b] = ++c, p[c] = c, sz[c] = 1;
            int ra = par(mp[a]), rb = par(mp[b]);
            if (ra^rb) sz[ra] += sz[rb], p[rb] = ra;
            printf("%d\n", sz[ra]);
        }
    }
    return 0;
}

2606번: 바이러스

https://www.acmicpc.net/problem/2606


$O(nα(n))$

union-find 자료구조를 이용해 1번과 같은 집합에 속한 컴퓨터 수를 구한다.

#include<cstdio>
int n, m, r, p[101];
int f(int x) { return x == p[x] ? x : p[x] = f(p[x]); }
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 0, x, y; i < m; i++) scanf("%d %d", &x, &y), p[f(x)] = f(y);
    for (int i = 2; i <= n; i++) r += f(1) == f(i);
    printf("%d", r);
    return 0;
}

12012번: Closing the Farm (Gold)

https://www.acmicpc.net/problem/12012


$O(n+m)$

쿼리를 반대로 봐서 해당 곳간을 열렸다고 표시하고 인접한 곳간들이 속한 집합들을 모두 합친다.
집합이 1개이면 YES 아니면 NO

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 2e5;
int n, m, ck[MXN + 1], a[MXN + 1], p[MXN + 1], r[MXN + 1], c;
vector<int> adj[MXN + 1];
int f(int h) { return h^p[h] ? p[h] = f(p[h]) : h; }
int main() {
        scanf("%d%d", &n, &m);
        for (int i = 0, x, y; i < m; i++) {
                scanf("%d%d", &x, &y);
                adj[x].push_back(y);
                adj[y].push_back(x);
        }
        for (int i = 1; i <= n; i++) scanf("%d", a + i), p[i] = i;
        for (int i = n; i; i--) {
                c++;
                for (auto it : adj[a[i]]) if (ck[it] && f(a[i]) ^ f(it)) {
                        p[f(it)] = f(a[i]);
                        c--;
                }
                ck[a[i]] = 1;
                r[i] = c == 1;
        }
        for (int i = 1; i <= n; i++) puts(r[i] ? "YES" : "NO");
        return 0;
}

10775번: 공항

https://www.acmicpc.net/problem/10775


$O(g+p)$

가능한 뒷 게이트에 비행기를 도킹한다.

#include<cstdio>
int g, p, par[100001], i, x;
int f(int x) { return x^par[x] ? par[x] = f(par[x]) : x; }
int main() {
    scanf("%d%d", &g, &p);
    for (i = 1; i <= g; i++) par[i] = i;
    for (i = 0; i < p; i++) {
        scanf("%d", &x);
        int r = f(x);
        if (!r) break;
        par[r] = r - 1;
    }
    printf("%d", i);
    return 0;
}

1717번: 집합의 표현

https://www.acmicpc.net/problem/1717


$O(n+m\alpha (n))$

union-find 자료구조를 사용한다.

#include<cstdio>
int n, m, p[1000001];
int f(int x) { return x^p[x] ? p[x] = f(p[x]) : x; }
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; i++) p[i] = i;
    for (int i = 0, x, y, z; i<m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        x ? puts(f(y) ^ f(z) ? "NO" : "YES") : p[f(y)] = f(z);
    }
    return 0;
}

1939번: 중량제한

https://www.acmicpc.net/problem/1939


$O(n+m\lg m)$

큰 가중치의 간선부터 보면서 연결된 지점들을 합집합 시킨다.
처음으로 시작 지점과 도착 지점이 같은 집합에 있게 될 때 보았던 간선의 가중치가 답이다.

#include<cstdio>
#include<algorithm>
using namespace std;
struct st {
    int x, y, z;
    bool operator<(st i) const {
        return z>i.z;
    }
}e[100000];
int n, m, p[10001], s, d;
int f(int x) { return x^p[x] ? p[x] = f(p[x]) : x; }
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i<m; i++) scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z);
    scanf("%d%d", &s, &d);
    sort(e, e + m);
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 0; i<m; i++) {
        p[f(e[i].x)] = f(e[i].y);
        if (f(s) == f(d)) { printf("%d", e[i].z); break; }
    }
    return 0;
}

11813번: GALAKSIJA

https://www.acmicpc.net/problem/11813


$O(n{\lg n}^2)$

w[i]: 1~i 경로상 가중치를 xor 한 것
p~q 경로상 가중치를 xor 한 것과 w[p]^w[q]이 같다.
고로 문제는 w[i]가 같은 쌍의 개수를 구하는 문제가 된다.
이는 map과 유니온 파인드 자료구조를 이용하면 위 시간복잡도에 해결할 수 있다.

간선을 삭제하는 쿼리들을 모두 받아놓은 뒤 반대로 나중 명령부터 처리하여 합집합하는 쿼리로 바꿔보자.
각 집합에 있는 w값 종류 수(집합의 크기)가 작은 쪽에서 큰 쪽으로 원소를 옮기며 합친다.
이 때 집합간 존재하는 w가 같은 쌍의 개수를 누적해준다.
합치는 명령은 총 O(nlgn)번 일어나며 각 원소를 합치는 연산이 O(lgn)이므로 위 시간복잡도가 나온다.

#include<cstdio>
#include<vector>
#include<map>
using namespace std;
const int MXN = 1e5;
int n, e[MXN][3], q[MXN + 1], w[MXN + 1];
vector<pair<int, int> > adj[MXN + 1];
long long r[MXN + 1], s;
struct st {
    int p[MXN + 1];
    map<int, int> mp[MXN + 1];
    void init() { for (int i = 1; i <= n; i++) p[i] = i, mp[i][w[i]]++; }
    int rt(int x) { return x^p[x] ? p[x] = rt(p[x]) : x; }
    void un(int x, int y) {
        int rx = rt(x), ry = rt(y);
        if (mp[rx].size() < mp[ry].size()) swap(rx, ry);
        for (auto it : mp[ry]) {
            s += (long long)mp[rx][it.first] * it.second;
            mp[rx][it.first] += it.second;
        }
        p[ry] = rx;
    }
}uf;
void dfs(int h, int p) {
    for (auto it : adj[h]) if (it.first^p) w[it.first] = w[h] ^ it.second, dfs(it.first, h);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i<n; i++) {
        scanf("%d%d%d", e[i], e[i] + 1, e[i] + 2);
        adj[e[i][0]].push_back({ e[i][1],e[i][2] });
        adj[e[i][1]].push_back({ e[i][0],e[i][2] });
    }
    for (int i = 1; i < n; i++) scanf("%d", q + i);
    dfs(1, 0);
    uf.init();
    for (int i = n; --i;) uf.un(e[q[i]][0], e[q[i]][1]), r[i] = s;
    for (int i = 1; i <= n; i++) printf("%lld\n", r[i]);
    return 0;
}

1981번: 배열에서 이동

https://www.acmicpc.net/problem/1981


$O(an^2)$ // a:배열에 있는 숫자 중 가장 큰 값, 에커먼 함수값을 상수 취급

각각의 하한값 0~200에 대해 상한값을 올려가며 그 사이의 지점들을 union-find를 이용해 합친다.
시작지점과 끝지점이 같은 집합에 있다면 제한 범위 내에 갈 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int n, cnt, p[10000], r = 999;
pair<int, int> s[10000];
int f(int h) { return h^p[h] ? p[h] = f(p[h]) : h; }
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) s[cnt].second = i*n + j, scanf("%d", &s[cnt++].first);
    sort(s, s + cnt);
    for (int i = 0; i <= 200; i++) {
        int ck[100][100] = { 0, };
        for (int j = 0; j < n*n; j++) p[j] = j;
        for (int j = 0; j < cnt; j++) if (s[j].first >= i) {
            ck[s[j].second / n][s[j].second%n] = 1;
            for (int k = 0; k < 4; k++) {
                int tx = s[j].second / n + fx[k], ty = s[j].second%n + fy[k];
                if (tx >= 0 && ty >= 0 && tx < n && ty < n && ck[tx][ty]) p[f(tx*n + ty)] = f(s[j].second);
            }
            if (f(0) == f(n*n - 1)) { r = min(r, s[j].first - i); break; }
        }
    }
    printf("%d", r);
    return 0;
}

2468번: 안전 영역

https://www.acmicpc.net/problem/2468


$O(n^2lgn)$

처음에 모든 지점이 물에 잠겨있고 높이가 큰 지점부터 드러난다고 생각하자.
현재 섬 개수가 c라고 하면 어떤 지점 x가 드러날때 추가로 드러난 섬의 개수는 1-(x 상하좌우에 이미 드러난 섬개수)이다.
c가 가장 클 때가 답이다.
유니온 파인드 자료구조를 이용해 여러 지점들을 하나의 섬으로 합칠 수 있을 것이다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 100, fx[] = { 1,-1,0,0 }, fy[] = { 0,0,1,-1 };
int n, par[MXN*MXN], r, c, ck[MXN][MXN];
int f(int x) { return x - par[x] ? par[x] = f(par[x]) : x; }
pair<int, int> p[MXN*MXN];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n*n; i++) scanf("%d", &p[i].first), p[i].second = par[i] = i;
    sort(p, p + n*n);
    for (int i = n*n - 1; i >= 0; i--) {
        c++;
        ck[p[i].second / n][p[i].second%n] = 1;
        for (int j = 0; j < 4; j++) {
            int tx = p[i].second / n + fx[j], ty = p[i].second%n + fy[j], t = tx*n + ty;
            if (tx >= 0 && ty >= 0 && tx < n && ty < n && ck[tx][ty] && f(t) != f(p[i].second)) par[f(t)] = f(p[i].second), c--;
        }
        if (!i || p[i - 1].first != p[i].first) r = r>c ? r : c;
    }
    printf("%d", r);
    return 0;
}