真·水·构造题


一开始的想法是,尽量的使得两个联通块最后才联通,这样就能使得不到最后一步,整张图无法联通

那么,用并查集维护一下,每次\(O(n^2)\)查询一下涉及的两个联通块加入新的边以后是否完整了

完整了,那么要返回两条边联通,否在返回不连通

但这样的话,最后一部分数据是要TLE的


然后发现….我可能制杖了啊

直接判断这条边是否是当前点连出的最后一条边即可

因为要保证每一个点都联通的话,至少存在一条边连入图中

这样的话,如果压个行,一行就解决了啊

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注