Min-hashing

무향 단순 그래프 $G = (V, E)$를 생각하자. 어떤 노드와 연결성이 비슷한 노드를 찾는 문제는 오래 연구된 주제이다. 이는 어떤 노드가 다른 노드와 관련 있는지를 판단하는 좋은 지표가 되기 때문이다. Facebook의 "친구 추천" 같은 서비스가 대표적인 응용 사례이다. 유사도를 형식화하기 위해 Jaccard 유사도 개념을 사용할 수 있으며, 이는 $|N(v_1) \cap N(v_2)| / |N(v_1) \cup N(v_2)|$로 정의된다. 여기서 $N(v) = \{u | (u, v) \in E\}$이다.

여기서는 대신 min-hashing 방법을 다룬다. 각 노드 $v$가 라벨 $l_v$를 가진다고 하자. 노드 $v$의 shingle 값 $s_v$는 $s_v = \min \{l_u | u \in N(v) \}$로 정의된다. 이 방법은 산업적 요구를 따라갈 만큼 효율적이며, 유사도를 재는 데도 훌륭한 지표이다. 무작위로 유일한 라벨을 부여했을 때, 이웃 집합 $N(v_1)$과 $N(v_2)$ 사이의 Jaccard 유사도는 노드 $v_1$과 $v_2$가 같은 shingle 값을 가질 확률의 비편향 추정량이다.

min-hashing의 변형을 생각해 보자. 라벨을 이전 반복의 shingle 값으로 삼아 min-hashing을 반복 수행한다. 이 변형에서 각 노드 $v$와 반복 횟수 $k$에 대해 값 $h^{(k)}_v$는 다음과 같이 정의된다.

$h^{(k)}_v = \begin{cases} s_v, & \text{if $k = 1$} \\ \min \{h^{(k-1)}_u | u \in N(v) \}, & \text{if $k \geq 2$} \end{cases}$

각 $k$에 대해 $c_k$를 $h^{(k)}_u = h^{(k)}_v$인 서로 다른 두 정점의 비순서쌍 $\{u, v\}$의 개수라 하자. 그러면 $k$가 커질수록 $c_k$는 어떻게 변할까? 이 문제에서 여러분의 과제는 $\max_{k \in \mathbb{N}} c_k$를 계산하는 것이다.

첫째 줄에 노드의 수와 간선의 수를 나타내는 두 양의 정수 $n$과 $m$ $(1 \leq n \leq 100\,000, 1 \leq m \leq 250\,000)$이 주어진다. 노드는 $1$부터 $n$까지 번호가 매겨진다. 이 번호는 노드의 라벨이 \textbf{아니다}.

둘째 줄에 $1$부터 $n$까지의 양의 정수를 한 번씩 포함하는 $n$개의 정수가 주어지며, $i$번째 수는 노드 $i$의 초기 라벨을 나타낸다.

다음 $m$개의 줄에 각각 두 정수가 주어진다. 이 중 $i$번째 줄에는 서로 다른 두 정수 $u_i$와 $v_i$ $(1 \leq u_i, v_i \leq n)$가 주어지며, $\{u_i, v_i\} \in E$임을 뜻한다.

입력은 자기 루프, 중복 간선, 차수가 $0$인 노드가 없도록 주어진다.

모든 양의 정수 $k$에 대한 $c_k$의 최댓값을 출력한다.