#面試題#Facebook 用戶都是雙向的好友，a是b的好友，那么b一定是a的。給定一個(gè)用戶列表，有些用戶是好友，有些不是，請(qǐng)判斷，這些用戶是否可以劃分為兩組，每組內(nèi)的用 戶，互相都不是好友。如果能，請(qǐng)給出這個(gè)劃分。原題見(jiàn)：
題目例子1：
用戶：{1, 2, 3}
好友關(guān)系：1-2， 2-3
劃分：{1,3} {2}
例子2：
用戶{1,2,3,4}
好友關(guān)系：1-2， 2-3， 3-4，4-1
劃分：{1, 3}{2, 4}
題目乍一看，感覺(jué)像是圖連通的問(wèn)題。細(xì)細(xì)品了下，貌似不是滴。。題目應(yīng)該可以解讀為有一個(gè)集合S，是否可以劃分成2個(gè)子集A,B，這2個(gè)子集滿足以下條件：
A∪B=S <-- 劃分為兩組
A∩B={}空 <-- 每組內(nèi)的用戶互相不為好友
既然如此，那么我想應(yīng)該很簡(jiǎn)單了，是不是？用2個(gè)set來(lái)表示子集A和B，一條一條關(guān)系處理，以例子2為例做個(gè)演練：
- 1-2，看下1或者2是否已經(jīng)存在在A和B里面了，如果不存在，1放進(jìn)A，2放進(jìn)B里面
- 2-3，看到2已經(jīng)在B里面了，先看下3是否也在B中了，如果在B中說(shuō)明不存在2個(gè)集合，退出，否則把3放到A中即可
- 3-4，3在A中，看4是否在A中，若存在退出，否則放4在B中。
- 4-1，4在B中，1不在B中，并且1已經(jīng)在A中，不需要繼續(xù)放了。
以上第2步，為啥要看3是否在B中？這其實(shí)就是做交集的過(guò)程，如果存在說(shuō)明已經(jīng)存在交集了。以上步驟結(jié)束后，A中是{1,3}，B中是{2,4}，現(xiàn)在就剩下最后一步了，就是要看這2個(gè)子集的并集是不是就是原始集合即可。這個(gè)很簡(jiǎn)單，只要過(guò)一遍原始集合，看下是否存在一個(gè)既不在A中，也不在B中就可以了。
代碼稍后更新。