• 길이가 소수인 에지들을 먼저 사용해서 도시들을 합쳐주고, 그 다음에 나머지 에지들을 사용해서 아직 떨어져있는 도시들을 합쳐주면 된다.
  • 소수인 에지의 가중치를 0, 소수가 아닌 에지의 가중치를 1로 두고 그래프를 만들어서 MST를 구하는 것과도 동일하다. 이렇게 하면 MST의 전체 가중치의 합이 q가 되고, p+q=c-1 이므로 p도 바로 구할수 있다 시간복잡도는 O(|E|log|E|)
• 각 에지 길이의 소수여부를 찾는 것은 O(m)에 소수 목록을 만들어 놓고서 (m=max(w)), 각각을 O(1)에 처리하면 된다.
• 총 시간복잡도는 O(|E|log|E| + max(w)) 이다
• 하지만, 이렇게 구현하면 구현 방식에 따라서 오류가 날 수 있다. 원인은 아마도 문제 데이터가 잘못된 것으로 추정된다. 처음에 주어진 도로의 목록을 이용해서 전체 도시를 연결할 수 없는 케이스가 있는 것 같다. 그냥 사이클이 생기지 않는 범위에서 최대한 소수인 에지를 사용해서 연결했을때의 사용한 에지의 개수 p만을 세어주고, q를 c-1-p로 계산해서 제출하면 통과가 되긴 한다. 조만간 데이터가 수정되어서 문제가 고쳐지든가, 언레 처리가 되든가 할거 같다..

"""Solution code for "BOJ 33550. Composius' Wrath".

- Problem link: https://www.acmicpc.net/problem/33550
- Solution link: http://www.teferi.net/ps/problems/boj/33550

Tags: [number theory] [disjoint set]
"""

import sys
from teflib import disjointset
from teflib import numtheory


def main():
    c, r = [int(x) for x in sys.stdin.readline().split()]

    dsu = disjointset.DisjointSet(c)
    pt = numtheory.PrimeTester()
    p = 0
    for _ in range(r):
        a, b, w = [int(x) for x in sys.stdin.readline().split()]
        a, b = a - 1, b - 1
        if pt.is_prime(w):
            if dsu.union_if_disjoint(a, b):
                p += 1

    print(p, c - 1 - p)


if __name__ == '__main__':
    main()

• Dependency:
  • teflib.numtheory.PrimeTester
  • teflib.disjointset.DisjointSet