本文主要是介绍二分图染色，CF1949I. Disks，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
Problem - 1949I - Codeforces
二、解题报告
1、思路分析
一种错误的判断是只要是偶数就不行，奇数都行（因为我就是这么错的
我们考虑一个圆增加，那么和它相邻的圆都会减小，那么对应的减小的圆的相邻圆又会变大
所以图中的圆只有两种状态——变小：变大
我们对每个连通块跑二染色二分图及染色法判定-CSDN博客
如果出现某个圆既变小又边大，或者变小的圆的数目不等于变大的圆的数目，那么该连通块无法变小
2、复杂度
时间复杂度： O(N^2)空间复杂度：O(N^2)
3、代码详解
n: int = int(input())points: list[list] = [] * n
g: list[list] = [[] for _ in range(n)]for i in range(n):x, y, r = map(int, input().split())for j in range(i):dx, dy, sr = x - points[j][0], y - points[j][1], r + points[j][2]if dx ** 2 + dy ** 2 == sr ** 2:g[i].append(j)g[j].append(i)points.append([x, y, r])ans = False
col = [0] * n
for i in range(n):if not col[i]:st = [i]col[i] = 1s1, s2 = 1, 0f = Truewhile st:u = st.pop()for v in g[u]:if not col[v]:col[v] = 3 - col[u]if col[v] == 1:s1 += 1else:s2 += 1st.append(v)elif col[v] == col[u]:f = Falseif f and s1 != s2:ans = Truebreak
print('YES' if ans else 'NO')这篇关于二分图染色，CF1949I. Disks的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
