每年，政府都會公布一萬個最常見的嬰兒名字和它們出現的頻率，也就是同名嬰兒的數量。有些名字有多種拼法，例如，John 和 Jon 本質上是相同的名字，但被當成了兩個名字公布出來。給定兩個列表，一個是名字及對應的頻率，另一個是本質相同的名字對。設計一個算法打印出每個真實名字的實際頻率。注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，則 John 與 Johnny 也相同，即它們有傳遞和對稱性。

在結果列表中，選擇字典序最小的名字作為真實名字。

示例：

輸入：names = [“John(15)”,“Jon(12)”,“Chris(13)”,“Kris(4)”,“Christopher(19)”], synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
輸出：[“John(27)”,“Chris(36)”]

代碼

class Solution {int[] strFa;public void  strInit()//并查集操作{for(int i=0;i<strFa.length;i++)strFa[i]=i;}public int  strFind(int x){if(x!=strFa[x])strFa[x]=strFind(strFa[x]);return strFa[x];}public void   strUnion(int x,int y){x=strFind(x);y=strFind(y);if(x==y) return;if(map.get(y).compareTo(map.get(strFa[x]))<0)//按字典序確定父節點strFa[x]=y;else strFa[y]=x;}  Map<Integer,String>map=new HashMap<>();public String[] trulyMostPopular(String[] names, String[] synonyms) {int n=names.length;strFa=new int[n];strInit();Map<String,Integer>map2=new HashMap<>(); int[] res=new int[n];for(int i=0;i<n;i++)//將名字和對應的編號用map記錄{String[] name=names[i].split("[()]");map.put(i,name[0]);map2.put(name[0],i);res[i]=Integer.parseInt(name[1]);}List<String> list=new ArrayList<>();for(String s:synonyms)//構建并查集{String name1=s.substring(1,s.indexOf(','));String name2=s.substring(s.indexOf(',')+1,s.length()-1);if(map2.containsKey(name1)&&map2.containsKey(name2))strUnion(map2.get(name1),map2.get(name2));}for(int i=0;i<n;i++)//將子節點的值累加到父節點{if(strFa[i]!=i) res[strFind(i)]+=res[i];}for(int i=0;i<n;i++)//返回所有的不相交的父節點if(strFa[i]==i){list.add(map.get(i)+'('+res[i]+')');}String[] ret=new String[list.size()];for(int i=0;i<list.size();i++)ret[i]=list.get(i);return ret;}
}