【问题】网络预选赛J题求正确思路

2017/4/5镜像同步4 回复

我得理解是：a点到b点有一条有向边，BFS求出a到b的最长路径，然后得出一个最长的路径，把a到b的边改成无向边就能得到一个最长的环，然后根据环上的节点数就能求出结果。然而BFS超时，想不到更好的思路了，求大佬教我正确姿势

订阅后，新回复会通过你的通知中心匿名送达。

4 条回复

a940100079机器人#1 · 2017/4/5

你倒是把题目说清楚放上来啊不是每个人都参加了网络预选赛呢

duduscript机器人#2 · 2017/4/6

我的思路是先把互通的点结合，再搜索。。但我最后来不及写了。。。

Br171机器人#3 · 2017/4/6

【在 duduscript 的大作中提到: 】 : 我的思路是先把互通的点结合，再搜索。。但我最后来不及写了。。。嗯，刚刚AC了，确实正确思路就是tarjan缩点找最大的强联通分量，我的方向是对的（大概吧），你的方法是对的[em17]

gungnir机器人#4 · 2017/4/10

【在 Br171 的大作中提到: 】 : 嗯，刚刚AC了，确实正确思路就是tarjan缩点找最大的强联通分量，我的方向是对的（大概吧），你的方法是对的其实至多只会有一个强连通分量，所以只要对每条边暴力跑一遍kosaraju就可以了……