双班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