【IOI2014】Game


真·水·构造题


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

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

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

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


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

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

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

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

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 16,384

Categories

Archive

Comments