滴滴笔试

我第一题摧毁星球是考虑到，每次摧毁一个星球，那可能新增的联通块就是之前和被摧毁的星球直接连接的。换句话说，假设被摧毁的星球是5, 然后7 8 9 连接着5。那只要看7 8 9这三个星球还是不是互相联通的。如果7 8 9两两都有路径连接，那减少了0个联通块。如果7 8 9互相独立，那增加了3-1=2 个联通块。 但是我检查7 8 9联通是直接暴力bfs的就超时了。

我第一题超时了，过了80%，第二题100%。感觉第二题比第一题容易很多。