HardNLPnlp-112

Mention Clustering

Problem

Cluster coreferent mentions using union-find. mentions is a list of mention strings and links is a list of [i, j] index pairs that must end up in the same cluster.

Return the clusters sorted by their alphabetically smallest mention, where each cluster is the alphabetically sorted list of its mentions.

Hint

Links are transitive, so union each pair and then group mentions by their root.

Test cases

case 1

in: [["Alice","alice","Bob"],[[0,1]]]

expected: [["Alice","alice"],["Bob"]]

case 2

in: [["a","b","c","d"],[[0,1],[1,2]]]

expected: [["a","b","c"],["d"]]

case 3

in: [["x","y"],[]]

expected: [["x"],["y"]]

case 4

in: [[],[]]

expected: []

Starter codePython

def mention_clustering(mentions, links):
    # Your code here
    pass

4 test cases · run your code against them in the editor