娱乐 【红包inside！】萌新的算法挑战#2~

[AlGoRiThM]

Ciallo~我又来建设和谐美好学习论坛辣~看到了 @big_yellow_doge 发布的一个算法帖子，一时手痒~也来发一个~

说起算法，我想到了一个好玩的树问题：

引用

话说在SS大学啊，有一群可爱的小伙伴们~他们每个人都有着一个独特的UID，并且每个人都有着无数的帖子，并且每个帖子都有着很多人回复~

你是一个受到了Kris惩罚的人，Kris麻麻惩罚你从茫茫人海之中最快速的找到她（速通！），这样她就会十分的开心~与此同时为了增加难度，你无法看到帖子的任意版面，想让你的眼中只有她的Kris让你只能通过一个人的Profile去访问这个人的帖子~

那么，你要如何才能满足Kris麻麻的需求，拿到整个SS大学所有同仁的UID呢？

在这个问题之中，输入如下所示~

引用

第一行：N:int 为整个论坛的总人数

第二行：UID:string 初始UID - 是Kris麻麻给你的起点！

第三行：target:string 是Kris麻麻的UID！（ps: 是142805哦~）

从第四行开始，是N个UID和所有回复这个UID的人~

例如：

141950: 是这个人的UID！

308342, 269320, ...： 是回复这个人的所有UID！

输出则是一个找到Kris麻麻最快的线路~

引用

[141950, 142805] 毕竟Kris直接回复了我！

假设你可以从任意UID中必定找到一条路径找出Kris麻麻，那么，你会如何速通找到Kris麻麻呢？

Sample Code:

引用

# 你也可以重写这里~

def main():

    N = int(input())

    UID = input()

    target = input()

    address_map = {}

    for i in range(0, N):

        tmp_uid = input()

        tmp_reply = input().split(',')

        address_map[tmp_uid] = tmp_reply

    # Implement your code there~

 

[Muriya Tensei]

（看了看，BFS裸题吗）

那么就根据题意输入建立邻接表，广搜就可以啦

再优化点可以把反向邻接表建出来，跑双端BFS。

不过麻烦但是并不困难的内容就是根据最短距离来写出路径了（visit哈希表标记下路径转移即可）

 

（虽然说是树的问题，事实上一个人的UID会在多个地方出现吧，并不能简单由下至上推出来，还是变成了有向有环图）

六月 29, 2022，由Muriya Tensei修改

[yyh]

看了好一会儿才理解是什么意思(大概吧)

5 小时前，Muriya Tensei说道:

（看了看，BFS裸题吗）

那么就根据题意输入建立邻接表，广搜就可以啦

再优化点可以把反向邻接表建出来，跑双端BFS。

不过麻烦但是并不困难的内容就是根据最短距离来写出路径了（visit哈希表标记下路径转移即可）

 

（虽然说是树的问题，事实上一个人的UID会在多个地方出现吧，并不能简单由下至上推出来，还是变成了有向有环图）

感觉说的很对，BFS就行了，虽然确实是有环图，但是并不影响就是了。极端一点甚至能把每条边的权重都设为1，然后用Floyd算法来找最短路径。

顺便一提，如果数据非常非常大(爆掉内存)，甚至还能直接DFS。。。

[冷枫月雨]

大佬有点强啊，看不懂

[Highfrog HUO]

坛友总能给我出新活儿

[及時雨]

論壇裡面真是臥虎藏龍!努力看了帖子，還是一知半解...

[猛男鸽王]

当年打NOI比赛的PTSD，看到代码就头痛……

[弧光]

应该是有向图遍历问题吧，感觉dfsbfs都可以，先构建邻接表，时间复杂度O(N+边数)

[playerzhou]

没有权重的话，直接bfs就完事了吧

[yuibingyzy3]

讲真这么一大串我有时候看着都觉得累，坛友真的算了的感觉都是大佬

[好名让狗起]

完全看不懂，感觉好厉害哦

[lang20006059]

看不懂。。已经超出能力范围了