10888 - 두 섬간의 이동

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

다리를 N-1개 지을때마다 그 때까지의 정부가 원하는 2개의 값 현황을 알려줘야한다. 정부가 원하는 값 2개는

• 두 섬 간에 왕래가 가능한 섬들 (i,j) (i<j) 쌍들의 개수
• 두 섬 (i,j)가 왕래 가능할 때 섬 i에서 섬 j까지 가기 위해 이용해야 하는 최소 다리 개수의 합

와 같다. 원하는 값을 설명하기 너무 기니까 왕래 가능한 쌍들의 개수를 pairs, 섬 들이 서로 이동하는데 필요한 최소 다리 개수의 합을 bridges라고 하겠다.

이 문제 역시 서로소 집합(Disjoint Set)으로 해결할 수 있다. pairs는 서로 연결된 섬들의 개수를 통해 알 수 있다.
서로 연결된 섬들의 개수를 $x$라 하면 $x=4$일 때 (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4) 로 6개이다.
i번째에서 i<j인 개수만큼 더하므로 $$ pairs = \sum_{k=1}^x k$$ 로 나타낼 수 있다.

그럼 bridges는 이러한 pairs개 만큼의 쌍들이 x-1개, x-2개, ..., 1개만큼 떨어져있으므로 전부 더한 값이다.
예를 들어 자세히 설명하자면, 섬 4개에 번호를 붙여서 1-2-3-4 라 하면, 1에서 나올 수 있는 쌍은 ~2, ~3, ~4까지이고 각각 최소 다리의 개수는 1, 2, 3 이므로 1에서 출발하는 경우는 1+2+3=6 이다. 2에서 출발하는 경우는 1+2 이고, 3에서 출발하는 경우는 1 (3-4. 1개)이다. 그럼 섬이 4개일 때 bridges는 1+(1+2)+(1+2+3)=10 이다.

수식으로는 $$\sum_{k=1}^{n-1} \left(\sum_{i=1}^k i\right) = \frac{(n-1)n(n+1)}{6}$$ 가 된다.

그리고 갈라져있던 두 집합이 합쳐지는 경우가 있는데, 이 때는 각 집합에서의 pairs와 bridges를 빼고 합친 후의 pairs와 bridges를 더해주면 전체 값은 유지되면서 갱신한 후에 센 값과 같다.

다음은 코딩할 때 사용한 샘플 입출력이다.

예제 입력

5
1 2 4 3

예제 출력

1 1
3 4
4 5
10 20

4195 - 친구 네트워크

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

네트워크의 구조와 상관없이 몇 명이 존재하는 지만 확인하면 되기 때문에 서로소 집합(Disjoint Set)으로 해결할 수 있다.

사용자의 아이디가 대소문자의 최대 20자라길래 $(26+26)^{20}$ 이면 long long으로 변환하면 편하겠거니 했는 데, 서로소 집합에서 번호를 나타내려면 이름마다 번호를 하나씩 붙이는 게 나을 것 같았다.

네트워크를 만들고 합치는 것은 간단하다. root배열을 각 원소들이 속해있는 집합의 번호라고 했을 때 p번과 q번을 합치려면 아래와 같다.

int root[100001];

int find(int k){
    if(k == root[k]) return k;
    return root[k] = find(root[k]);
}

void merge(int p, int q){
    p = find(p);
    q = find(q);
    if(p != q) root[q] = p;
}

네트워크에 속해있는 원소들의 수는 어떻게 세야할까. 위 코드대로라면 원소는 대충 아래와 같이 있을 것이다.

[그림 1]

화살표로 가리키는 것은 부모-자식의 관계가 아니라 집합의 번호이다. 위처럼 두 집합은 초록색 원소가 그 집합의 대표라고 할 수 있다. 그럼 집합의 개수는 초록색 원소 위에 있는 숫자라고 하자.

(q가 p에 흡수되는) 위 코드를 참고하여 두 집합을 합치면 [그림 2]와 같이 나타낼 수 있다.

[그림 2]

q의 개수를 p에 더해주고, q는 1개(나중에 다른 집합으로 옮겨질 것을 우려한다면)로 바꿔주면 된다.

나머지 원소들의 집합 번호를 바꾸지 않아도 되는 것은, 나중에 조회할 때 find(e) 를 해주면 다시 갱신되기 때문이다.

서로 다른 이름이 N개의 줄마다 2개씩 나올 수 있으므로 배열의 범위는 $2N$으로 설정했다.