三金老师

分类

题解(25)

/ 注册

全部文章（共3篇）

【每日一题】图的遍历 (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

【每日一题】黑白树（思维+dfs）

Solutionemm昨天看了但是没有写出来，因为不会处理回溯过程中的更有利涂黑的情况。题解很巧妙，没想到可以用另外一个数组d来记录可以最多涂黑到哪个点，当数组d为0时就代表需要多操作一次，而这个更新操作次数正是这道题的灵魂所在。简单来说就是：更新回溯过程中最远可到达的距离更新回溯过程中...

dfs 每日一题思维

2020-04-08

0 614