首页 > 其他 > 详细

AGC011-C Squared Graph

时间:2020-02-24 12:33:14      阅读:57      评论:0      收藏:0      [点我收藏+]

题意

给定一个\(n\)个点\(m\)条边的图,构建一个\(n^2\)个点的图,新图的每个点都可以看成一个二元组,新图上的点\((a,b)和(a′,b′)\)之间有边,当且仅当原图中\((a,a′),(b,b′)\)之间有边,问新图的联通块个数。

做法

首先没有邻点的点拿出来随便搞

剩下考虑联通块

  • 块内点对
    二分图的话,贡献为\(2\)
    否则,贡献为\(1\)
  • 块间点对
    二分图-二分图,贡献为\(2\)
    二分图-其他,贡献为\(1\)
    其他-其他,贡献为\(1\)

题外话

有没有觉得跟某题很像啊,idea打这来的

AGC011-C Squared Graph

原文:https://www.cnblogs.com/Grice/p/12355993.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!