[計程] 雙班hw題目參考解法

[barry800414 (小銘)]

雙班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
→ robertabcd:話說上面助教那篇有講
→ robertabcd:                    有多筆測資
推 bang5115:感覺記憶體沒什麼限制  好像不太需要注意會爆掉XD
推 ilovejun:推!
推 asdfghjkl202:囧耶！我也是降寫可是最後一個測資會爆......
推 Dorapika:推！或是可以想成stack，把新加的朋友都設成top。
推 swem:這題其實沒有要求太好的效率  暴搜是可以接受的 :p
→ swem:不過你列的 befriend 這方法不錯
→ barry800414:從拉球那聽到更好的方法了>  <
→ barry800414:然後其實後來我發現這個方法並沒有節省空間...
推 yuscvscv:如果用前向星的效果會不會比較好? //印象list蠻慢的