雙班hw9 common friends http://palcourse.csie.ntu.edu.tw/judgegirl/problem/c2009/homework/ assignment9/CommonFriend.htm 我想說有人問 而且我的讀書會是在雙班deadline之後 所以就想說PO版了 希望有所幫助 這一題的瓶頸就在於你沒辦法開int relation[25000][25000]; 這麼大的空間 而且這方法效率也不好 所以要用鏈結串列來節省空間了 想法大致是這樣: 先有一個結構 裡面存index 和一個指向自己結構的指標(即鏈結串列的node) typedef struct node { int index; struct node *next; } 接著我開兩個 25001大小的"指標"陣列 25001個都是Node 指標 即 Node *relation[25001]; 和 Node *tail[25001]; 用途? 假設 5這個人有10 20 15這三個朋友 8這個人有15 10 19這三位朋友 那結構會長這樣: relation pointer array : ───────────────────── │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │.... ───────────────────── ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ── ── │10│ │15│ ── ── ↓ ↓ ── ── │20│ │10│ ── ── tail[5] =↓ tail[8] =↓ ── ── │15│ │19│ ── ── ↓ ↓ 意即 relation[5]下面所指到的index(10 20 15)都是他的朋友 那麼 為什麼要tail pointer array呢? 我每次都把tail指到最後一個節點 那麼我在新增節點時候就不用從頭開始找結尾了 直接tail[i]->next=newptr; tail[i]=tail[i]->next; 就OK了!! 絕對可以省很多時間 那如何尋找共同朋友呢? 就舉上面為例 我想知道5和8的共同朋友 那麼 因為大小沒有排序 如果 5的每一個朋友都向8的朋友爆搜 會非常沒有效率(O(n^2)) 所以先開個陣列叫befriend[25001]; 以及計數器 count=0; 先將其歸0 接著把5的所有朋友 即10 20 15 befriend[10]=1; befriend[20]=1; befriend[15]=1; 那麼 再找 8的所有朋友 即 15 10 19 檢查 if(befriend[15]==1) count++; if(befriend[19]==1) count++; if(befriend[10]==1) count++; 也就是先把5的朋友在陣列上做記號 再看看8的朋友有幾個跟5一樣 這樣檢查完count會是2 接著printf("%d\n",count); 就可以了 然後 其實這個方法 在資料結構上是有專有名詞的 叫adjacency list 相鄰串列 是一種常見的存圖方法 (另一種是我們較直覺想到的 即relation[a][b]=1 表示a b是朋友) 叫 adjacency matrix 相鄰矩陣 有興趣的人可以上網查看看 然後 當你拿到9分之後(而且是第一筆測資錯) 趕快去問資工之王 王挺宇吧XD 這題很心機 其實是多筆測資 (只有第一筆測資是多筆測資="=) 感謝資工之王 王挺宇的幫助=) 剩下的大家加油!! coding 還是要自己來的 Happy Christmas Eve! --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.241.197