大概偷了這么些題目吧：
剛看到這題的時(shí)候我是有點(diǎn)開(kāi)心的，因?yàn)楹雎缘暨@些文字就發(fā)現(xiàn)簡(jiǎn)直跟Leetcode Number of Island 那道題一樣欣鳖。
【事實(shí)證明不一樣 T^T...】
用Number of Island那題的解法可以過(guò)sample test case调窍。 但是面對(duì)一些很坑爹的case是過(guò)不去的低淡。
比如
10000
01000
00100
00010
00011
Expected Answer: 5
DFS到第四行的時(shí)候會(huì)順便往下走，然后把第五行第四個(gè)元素變成0寻狂，然后繼續(xù)往右走岁经，然后把第五行最后一個(gè)變成0.
這樣總共他就會(huì)計(jì)算出 有4個(gè)isolated zoombie groups.
我這里其實(shí)應(yīng)該最后多加一個(gè)if case.
if(arr[row][col] !=1 || arr[col][row]) != 1的話，也就是 你認(rèn)我為朋友蛇券，我不認(rèn)識(shí)你的話缀壤，這樣就不應(yīng)該算一伙的。
T^T 就差一個(gè)if case 沒(méi)想到纠亚。塘慕。〉侔考的時(shí)候還是太緊張了
Edit on 7/28.
晚上逛Leetcode图呢，本來(lái)以為Friend Circles是約瑟夫問(wèn)題 結(jié)果發(fā)現(xiàn)竟然就是Pocket_gems的zoombie!!!
看完答案發(fā)現(xiàn)。。蛤织。這道題比我想的要難的多的多的多赴叹。。指蚜。Pocket Gems ヽ(*乞巧。>Д<)o゜
主流的做法大概可以分為DFS 和 Union Find （完全超出我之前準(zhǔn)備的。摊鸡。绽媒。）
Adjancy Matrix:?
左邊rows是ith person, cols是其他所有人。1表示是朋友免猾，0表示不是朋友是辕。 用DFS的方式，先從Person 0看一下誰(shuí)是他朋友掸刊，看到person2 是他朋友免糕，然后recursively 去到person2 看person2 有誰(shuí)是朋友， 然后全部visit一遍忧侧。到最后停下來(lái)的時(shí)候就代表已經(jīng)把Person 0的所有transistive 朋友圈看完了石窑。沿途中，會(huì)把經(jīng)過(guò)的人化成同一個(gè)group的人蚓炬。下一輪開(kāi)始的時(shí)候松逊，會(huì)挑不在之前的group里的人，也就是unvisisted的肯夏。
一開(kāi)始initialize root array. 每一個(gè)person 一開(kāi)始都以自己為單位经宏， 編號(hào)為index。如果就此結(jié)束驯击，那么我們會(huì)有N個(gè)isolated groups. 但是現(xiàn)在要開(kāi)始搜索朋友圈烁兰。iterate People List. 對(duì)于每一個(gè)人，traverse to 他的好友徊都，也就是 M[i][j] == 1的人沪斟。 比如說(shuō)person0的好友有person1，我們對(duì)index [0,1] apply Union Find暇矫。 發(fā)現(xiàn)目前Person0 的root為0, person1的root為1. 但是他們又是好朋友主之。 所以我們merge 他們的root，讓root[1] = 0 也就是被traverse的人歸到person0的group里李根。?
最后看一下Root的列表槽奕。 跟person本身index一樣的才算一個(gè)隊(duì)伍，因?yàn)楦约翰灰粯觟ndex的表示這個(gè)人已經(jīng)進(jìn)了另一個(gè)人的隊(duì)伍里去了房轿。
這個(gè)解法用root[] 來(lái)keep track of parents. 一般的unionFind會(huì)定義一個(gè)Find方法粤攒，來(lái)找parents所森。
跟這道題相似的類型還有 Graph Valid Tree, Number of Island 2, ?Number of Connected Components.
