三金老师

题解

/ 注册

全部文章 / 题解（共2篇）

【每日一题】图的遍历 (dfs / 染色+判奇环)

Solution题意:无向图有n个点，从点1开始遍历，每次走两步，遍历整个图。问最少加几条边，可以完整的遍历整个图。思路：首先可以想到的是如果图不连通，那么答案至少需要 (联通块的数目-1) 来把各个联通块连起来。而走两步的话，不难联想到奇偶形，考虑奇环的话两步可以到达环内任意一点，所以只要连通后...

dfs 联通块每日一题

2020-05-21

0 930

【每日一题】边的染色（dfs+思维 / 联通块+xor）

Solution题意：给定一个无向图，有一些边已经染色，求让你染色剩下的边使得每个环的异或和都为0的方案数。好难想!好难想!好难想!重要的事情要说三遍! 1.思维点：题解很巧妙，把对边染色转移到对点染色，取边为两个端点的xor，这样的话每个环的异或和肯定为0，因为每个点都xor了两次~ 2.答案的...

dfs 联通块每日一题思维

2020-04-24

0 738