基环树
图中只存在一个环的图就是基环树，分为有向图和无向图 无向图求基环树可以使用bfs ： 先统计入度，然后每次对队列中元素删边，把删后度数为1的点入队，bfs结束后，所有度数 > 1的点就是环上的点，如果只需要求一个点，可以使用dfs，出现了两次的点说明必然有环。 想法1 ： 可以通过先找出基环树的环， 之后分别对除了环以外的每个点的子树进行操作，把信息合并到环上，之后问题就集中为处理一个环上问题， 想法2 ： 可以先找出基环树的环， 之后删掉基环树上某一条边， 将基环树变成一个树，处理树上问题 寻找环的办法1 ： 对于无向图， 使用拓补排序，最后剩下的度数 > 1 的点就是环上的点1 2 : 对于有向图， 使用dfs 寻找，出现了vis两次的点就是环上一个点123456auto check_c = [&](auto self, i64 u) -> int { vis[u] = 1; int now = fa[u]; if (vis[now]) return now; else...
欧拉回路
欧拉回路是这样一个东西（个人理解） ： 从图上某个点出发，每条边不能重复经过，然后从这个点开始把所有的点和边走一遍（同时满足每条边不能重复）后回到这个点。 怎么求？ 一种办法是Fluery , 即每次只找不是桥的边bfs， 当每个点和边都进队后再处理桥， 如果图不连通或者经过桥之后无法遍历整个图，则没有欧拉回路，否则就找到了欧拉回路， 由于这样实现需要先tarjan缩强连通分量后记录桥的位置，之后再每个点遍历，需要时间复杂度大约是O(n ^ 2), 太不牛，我们换下一个算法 Hierholzer算法 （不是这什么鬼名字也太长……）我直接把函数名字写成dfs了，板子如下（自己实现的用起来自己舒服）123456789vector<int> now(n + 1);stack<int> s;auto dfs = [&](auto self, int u) -> void { for (int i = now[u]; i < e[u].size(); i = now[u]) { now[u]++; ...