←_←

题目链接题意给你一副无向图，求桥数量 和 属于多个环的边数量思路求桥好写，属于多个环的边数，仙人掌判断恰好这么处理，求点双，点双内的边数大于点数则点双内每条边属于多个环。代码#include <bits/stdc++.h>using namespace std;#define ll long longconst int N = 10005;vector<i...

题目链接题意判断一个有向图是不是仙人掌图思路思路看这代码看这据说数据水，这个比较详细应该正确tarjan 先判断图是否强连通再判断是否为仙人掌假设图强连通，结论如下仙人掌图的 DFS 树没有横向边。设某个点 v 有 a(v)个儿子的 Low 值小于 DFS(v)，同时 v 自己有 b(v)条逆向边，那么 a(v)+b(v)<2。代码#include <bits...

随便总结下给自己以后回忆，结论全凭感觉加一点点实践，如有错误欢迎指出。图为单向边需要vis标记是否在队列图为无向边求双边连通，求桥无重边 深搜不搜爹，递归多传个爹是谁有重边 深搜不搜同边，链式前向星存图，同边的id差1求割点 搜不到返祖边即是割点，low[v] &amp;amp;gt;= dfn[u]求割边 儿子搜不到返回爹的边即割边，low[v] &amp;amp;gt; dfn[u]...

[题目链接][http://acm.hdu.edu.cn/showproblem.php?pid=4612]题意给你一个连通图，你可以任意加一条边，求最小桥数量。思路先用tarjan求所有桥，将双边连通的点缩点，再对缩点后的新图加上桥，得到cnt新图的点数。求新图的直径，在直径两端加一条边最优（可以消去最多的桥），答案即，新图点数-1-直径长度。代码#include &amp;amp;lt;stdi...

题目链接思路tarjan求强连通分量模板题代码#include &amp;lt;bits/stdc++.h&amp;gt;using namespace std;int low[10005], dfn[10005], vis[10005], tot = 0, n, ans;stack&amp;lt;int&amp;gt; st;vector&amp;lt;int&amp;gt; e[10005];void tarjan(i...